Fast exact algorithm for subset sum problem in Java











up vote
2
down vote

favorite












I have implemented an $mathcal{O}(N2^{N/2})$ algorithm for subset sum problem described in Wikipedia.



That is what I have:



SubsetSumFinder.java:



package net.coderodde.combinatorics;

import java.util.List;

/**
* This interface defines the API for a subset sum algorithm.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Apr 25, 2016)
*/
public interface SubsetSumFinder {

/**
* Attempts to find a subset of {@code data}, such that all integers in the
* subset sum to {@code sum}.
*
* @param data the list of integers.
* @param sum the requested sum.
* @return a subset summing to {@code sum} or {@code null} if there is no
* such.
*/
public List<Integer> findSubsetWithSum(final List<Integer> data,
final int sum);
}


CombinationIterable.java (already reviewed):



package net.coderodde.combinatorics.support;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

public class CombinationIterable<T> implements Iterable<List<T>> {

private final List<T> allElements;

public CombinationIterable(List<T> allElements) {
this.allElements = new ArrayList<>(allElements);
}

@Override
public Iterator<List<T>> iterator() {
return new CombinationIterator<>(allElements);
}

private static final class CombinationIterator<T>
implements Iterator<List<T>> {

private final List<T> allElements;
private final int indices;
private List<T> nextCombination;
private int currentCombinationSize;

CombinationIterator(List<T> allElements) {
this.allElements = new ArrayList<>(allElements);
this.indices = new int[allElements.size()];

if (!allElements.isEmpty()) {
// Create the first combination.
currentCombinationSize = 1;
nextCombination = new ArrayList<>(1);
nextCombination.add(allElements.get(0));
}
}

@Override
public boolean hasNext() {
return nextCombination != null;
}

@Override
public List<T> next() {
if (nextCombination == null) {
throw new NoSuchElementException("No combinations left.");
}

List<T> combination = nextCombination;
generateNextCombination();
return combination;
}

private void loadCombination() {
List<T> combination = new ArrayList<>(currentCombinationSize);

for (int i = 0; i < currentCombinationSize; ++i) {
combination.add(allElements.get(indices[i]));
}

this.nextCombination = combination;
}

private void generateNextCombination() {
if (indices[currentCombinationSize - 1] < indices.length - 1) {
indices[currentCombinationSize - 1]++;
loadCombination();
return;
}

for (int i = currentCombinationSize - 2; i >= 0; --i) {
if (indices[i] < indices[i + 1] - 1) {
indices[i]++;

for (int j = i + 1; j < currentCombinationSize; ++j) {
indices[j] = indices[j - 1] + 1;
}

loadCombination();
return;
}
}

++currentCombinationSize;

if (currentCombinationSize > indices.length) {
this.nextCombination = null;
return;
}

for (int i = 0; i < currentCombinationSize; ++i) {
indices[i] = i;
}

loadCombination();
}
}
}


FastSubsetSumFinder.java:



package net.coderodde.combinatorics.support;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import net.coderodde.combinatorics.SubsetSumFinder;

/**
* This class implements a faster exact subset sum algorithm.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Apr 25, 2016)
*/
public class FastSubsetSumFinder implements SubsetSumFinder {

@Override
public List<Integer> findSubsetWithSum(List<Integer> data, int sum) {
final List<Integer> list1 = new ArrayList<>();
final List<Integer> list2 = new ArrayList<>();
final int size = data.size();

for (int i = 0; i < size / 2; ++i) {
list1.add(data.get(i));
}

for (int i = size / 2; i < size; ++i) {
list2.add(data.get(i));
}

final List<List<Integer>> combinationList1 = new ArrayList<>();
final List<List<Integer>> combinationList2 = new ArrayList<>();
final Map<List<Integer>, Integer> map = new HashMap<>();

for (final List<Integer> subset : new CombinationIterable<>(list1)) {
map.put(subset, sum(subset));
combinationList1.add(subset);
}

for (final List<Integer> subset : new CombinationIterable<>(list2)) {
map.put(subset, sum(subset));
combinationList2.add(subset);
}

final Comparator<List<Integer>> comparator = new SubsetComparator(map);

Collections.sort(combinationList1, comparator);
Collections.sort(combinationList2, comparator);

int index1 = 0;
int index2 = combinationList2.size() - 1;

while (true) {
int totalSum = map.get(combinationList1.get(index1)) +
map.get(combinationList2.get(index2));

if (totalSum < sum) {
++index1;
} else if (totalSum > sum) {
--index2;
} else {
final List<Integer> solution = new ArrayList<>(size);
solution.addAll(combinationList1.get(index1));
solution.addAll(combinationList2.get(index2));
return solution;
}

if (index1 == combinationList1.size()
|| index2 == -1) {
return null;
}
}
}

private int sum(final List<Integer> subset) {
int sum = 0;

for (final Integer i : subset) {
sum += i;
}

return sum;
}

private static final class SubsetComparator
implements Comparator<List<Integer>> {

private final Map<List<Integer>, Integer> map;

SubsetComparator(final Map<List<Integer>, Integer> map) {
this.map = map;
}

@Override
public int compare(List<Integer> o1, List<Integer> o2) {
final int sum1 = map.get(o1);
final int sum2 = map.get(o2);
return Integer.compare(sum1, sum2);
}
}
}


NaiveSubsetSumFinder.java:



package net.coderodde.combinatorics.support;

import java.util.List;
import net.coderodde.combinatorics.SubsetSumFinder;

/**
* This class implements a naive exact algorithm for solving the subset sum
* problem.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Apr 25, 2016)
*/
public class NaiveSubsetSumFinder implements SubsetSumFinder {

@Override
public List<Integer> findSubsetWithSum(List<Integer> data, int sum) {
final CombinationIterable<Integer> iterable =
new CombinationIterable<>(data);

for (final List<Integer> subset : iterable) {
if (sum(subset) == sum) {
return subset;
}
}

return null;
}

private int sum(final List<Integer> subset) {
int sum = 0;

for (final Integer integer : subset) {
sum += integer;
}

return sum;
}
}


Demo.java:



import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import net.coderodde.combinatorics.SubsetSumFinder;
import net.coderodde.combinatorics.support.FastSubsetSumFinder;
import net.coderodde.combinatorics.support.NaiveSubsetSumFinder;

public class Demo {

private static final int N = 25;
private static final int N_INTEGERS = 100;
private static final int NEEDLE = 1000;

public static void main(final String args) {
final long seed = System.nanoTime();
final Random random = new Random(seed);
final List<Integer> data = new ArrayList<>(N);

System.out.println("Seed = " + seed);

for (int i = 0; i < N; ++i) {
data.add(random.nextInt(N_INTEGERS));
}

final SubsetSumFinder finderNaive = new NaiveSubsetSumFinder();
final SubsetSumFinder finderFast = new FastSubsetSumFinder();

long startTime = System.nanoTime();
final List<Integer> subset1 =
finderNaive.findSubsetWithSum(data, NEEDLE);
long endTime = System.nanoTime();

System.out.printf("NaiveSubsetSumFinder: %5.0f milliseconds. " +
"Result: %s, valid: %b.n",
(endTime - startTime) / 1e6,
subset1,
sum(subset1) == NEEDLE);

startTime = System.nanoTime();
final List<Integer> subset2 =
finderFast.findSubsetWithSum(data, NEEDLE);
endTime = System.nanoTime();

System.out.printf("FastSubsetSumFinder: %5.0f milliseconds. " +
"Result: %s, valid: %b.n",
(endTime - startTime) / 1e6,
subset2,
sum(subset2) == NEEDLE);
}

private static int sum(final List<Integer> subset) {
int sum = 0;

for (final Integer i : subset) {
sum += i;
}

return sum;
}
}


The performance figures are as follows:





NaiveSubsetSumFinder: 3371 milliseconds.
FastSubsetSumFinder: 115 milliseconds.



Any critique much appreciated.










share|improve this question
























  • I can see from your numbers that Fast is actually faster than naive, but your perf testing technique is flawed. Java heavily optimises code as it executes, so you need to run through your code quite a lot to allow the jvm to complete doing that before you start measuring performance.
    – Engineer Dollery
    Apr 27 '16 at 14:53










  • Yeah, I know: the warmup effect. In case you don't trust the figures, roll your own warmup code (I am not sure whether it is O.K. to edit the question). However, I am confident that the Fast implementation has better time complexity.
    – coderodde
    Apr 27 '16 at 14:56















up vote
2
down vote

favorite












I have implemented an $mathcal{O}(N2^{N/2})$ algorithm for subset sum problem described in Wikipedia.



That is what I have:



SubsetSumFinder.java:



package net.coderodde.combinatorics;

import java.util.List;

/**
* This interface defines the API for a subset sum algorithm.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Apr 25, 2016)
*/
public interface SubsetSumFinder {

/**
* Attempts to find a subset of {@code data}, such that all integers in the
* subset sum to {@code sum}.
*
* @param data the list of integers.
* @param sum the requested sum.
* @return a subset summing to {@code sum} or {@code null} if there is no
* such.
*/
public List<Integer> findSubsetWithSum(final List<Integer> data,
final int sum);
}


CombinationIterable.java (already reviewed):



package net.coderodde.combinatorics.support;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

public class CombinationIterable<T> implements Iterable<List<T>> {

private final List<T> allElements;

public CombinationIterable(List<T> allElements) {
this.allElements = new ArrayList<>(allElements);
}

@Override
public Iterator<List<T>> iterator() {
return new CombinationIterator<>(allElements);
}

private static final class CombinationIterator<T>
implements Iterator<List<T>> {

private final List<T> allElements;
private final int indices;
private List<T> nextCombination;
private int currentCombinationSize;

CombinationIterator(List<T> allElements) {
this.allElements = new ArrayList<>(allElements);
this.indices = new int[allElements.size()];

if (!allElements.isEmpty()) {
// Create the first combination.
currentCombinationSize = 1;
nextCombination = new ArrayList<>(1);
nextCombination.add(allElements.get(0));
}
}

@Override
public boolean hasNext() {
return nextCombination != null;
}

@Override
public List<T> next() {
if (nextCombination == null) {
throw new NoSuchElementException("No combinations left.");
}

List<T> combination = nextCombination;
generateNextCombination();
return combination;
}

private void loadCombination() {
List<T> combination = new ArrayList<>(currentCombinationSize);

for (int i = 0; i < currentCombinationSize; ++i) {
combination.add(allElements.get(indices[i]));
}

this.nextCombination = combination;
}

private void generateNextCombination() {
if (indices[currentCombinationSize - 1] < indices.length - 1) {
indices[currentCombinationSize - 1]++;
loadCombination();
return;
}

for (int i = currentCombinationSize - 2; i >= 0; --i) {
if (indices[i] < indices[i + 1] - 1) {
indices[i]++;

for (int j = i + 1; j < currentCombinationSize; ++j) {
indices[j] = indices[j - 1] + 1;
}

loadCombination();
return;
}
}

++currentCombinationSize;

if (currentCombinationSize > indices.length) {
this.nextCombination = null;
return;
}

for (int i = 0; i < currentCombinationSize; ++i) {
indices[i] = i;
}

loadCombination();
}
}
}


FastSubsetSumFinder.java:



package net.coderodde.combinatorics.support;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import net.coderodde.combinatorics.SubsetSumFinder;

/**
* This class implements a faster exact subset sum algorithm.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Apr 25, 2016)
*/
public class FastSubsetSumFinder implements SubsetSumFinder {

@Override
public List<Integer> findSubsetWithSum(List<Integer> data, int sum) {
final List<Integer> list1 = new ArrayList<>();
final List<Integer> list2 = new ArrayList<>();
final int size = data.size();

for (int i = 0; i < size / 2; ++i) {
list1.add(data.get(i));
}

for (int i = size / 2; i < size; ++i) {
list2.add(data.get(i));
}

final List<List<Integer>> combinationList1 = new ArrayList<>();
final List<List<Integer>> combinationList2 = new ArrayList<>();
final Map<List<Integer>, Integer> map = new HashMap<>();

for (final List<Integer> subset : new CombinationIterable<>(list1)) {
map.put(subset, sum(subset));
combinationList1.add(subset);
}

for (final List<Integer> subset : new CombinationIterable<>(list2)) {
map.put(subset, sum(subset));
combinationList2.add(subset);
}

final Comparator<List<Integer>> comparator = new SubsetComparator(map);

Collections.sort(combinationList1, comparator);
Collections.sort(combinationList2, comparator);

int index1 = 0;
int index2 = combinationList2.size() - 1;

while (true) {
int totalSum = map.get(combinationList1.get(index1)) +
map.get(combinationList2.get(index2));

if (totalSum < sum) {
++index1;
} else if (totalSum > sum) {
--index2;
} else {
final List<Integer> solution = new ArrayList<>(size);
solution.addAll(combinationList1.get(index1));
solution.addAll(combinationList2.get(index2));
return solution;
}

if (index1 == combinationList1.size()
|| index2 == -1) {
return null;
}
}
}

private int sum(final List<Integer> subset) {
int sum = 0;

for (final Integer i : subset) {
sum += i;
}

return sum;
}

private static final class SubsetComparator
implements Comparator<List<Integer>> {

private final Map<List<Integer>, Integer> map;

SubsetComparator(final Map<List<Integer>, Integer> map) {
this.map = map;
}

@Override
public int compare(List<Integer> o1, List<Integer> o2) {
final int sum1 = map.get(o1);
final int sum2 = map.get(o2);
return Integer.compare(sum1, sum2);
}
}
}


NaiveSubsetSumFinder.java:



package net.coderodde.combinatorics.support;

import java.util.List;
import net.coderodde.combinatorics.SubsetSumFinder;

/**
* This class implements a naive exact algorithm for solving the subset sum
* problem.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Apr 25, 2016)
*/
public class NaiveSubsetSumFinder implements SubsetSumFinder {

@Override
public List<Integer> findSubsetWithSum(List<Integer> data, int sum) {
final CombinationIterable<Integer> iterable =
new CombinationIterable<>(data);

for (final List<Integer> subset : iterable) {
if (sum(subset) == sum) {
return subset;
}
}

return null;
}

private int sum(final List<Integer> subset) {
int sum = 0;

for (final Integer integer : subset) {
sum += integer;
}

return sum;
}
}


Demo.java:



import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import net.coderodde.combinatorics.SubsetSumFinder;
import net.coderodde.combinatorics.support.FastSubsetSumFinder;
import net.coderodde.combinatorics.support.NaiveSubsetSumFinder;

public class Demo {

private static final int N = 25;
private static final int N_INTEGERS = 100;
private static final int NEEDLE = 1000;

public static void main(final String args) {
final long seed = System.nanoTime();
final Random random = new Random(seed);
final List<Integer> data = new ArrayList<>(N);

System.out.println("Seed = " + seed);

for (int i = 0; i < N; ++i) {
data.add(random.nextInt(N_INTEGERS));
}

final SubsetSumFinder finderNaive = new NaiveSubsetSumFinder();
final SubsetSumFinder finderFast = new FastSubsetSumFinder();

long startTime = System.nanoTime();
final List<Integer> subset1 =
finderNaive.findSubsetWithSum(data, NEEDLE);
long endTime = System.nanoTime();

System.out.printf("NaiveSubsetSumFinder: %5.0f milliseconds. " +
"Result: %s, valid: %b.n",
(endTime - startTime) / 1e6,
subset1,
sum(subset1) == NEEDLE);

startTime = System.nanoTime();
final List<Integer> subset2 =
finderFast.findSubsetWithSum(data, NEEDLE);
endTime = System.nanoTime();

System.out.printf("FastSubsetSumFinder: %5.0f milliseconds. " +
"Result: %s, valid: %b.n",
(endTime - startTime) / 1e6,
subset2,
sum(subset2) == NEEDLE);
}

private static int sum(final List<Integer> subset) {
int sum = 0;

for (final Integer i : subset) {
sum += i;
}

return sum;
}
}


The performance figures are as follows:





NaiveSubsetSumFinder: 3371 milliseconds.
FastSubsetSumFinder: 115 milliseconds.



Any critique much appreciated.










share|improve this question
























  • I can see from your numbers that Fast is actually faster than naive, but your perf testing technique is flawed. Java heavily optimises code as it executes, so you need to run through your code quite a lot to allow the jvm to complete doing that before you start measuring performance.
    – Engineer Dollery
    Apr 27 '16 at 14:53










  • Yeah, I know: the warmup effect. In case you don't trust the figures, roll your own warmup code (I am not sure whether it is O.K. to edit the question). However, I am confident that the Fast implementation has better time complexity.
    – coderodde
    Apr 27 '16 at 14:56













up vote
2
down vote

favorite









up vote
2
down vote

favorite











I have implemented an $mathcal{O}(N2^{N/2})$ algorithm for subset sum problem described in Wikipedia.



That is what I have:



SubsetSumFinder.java:



package net.coderodde.combinatorics;

import java.util.List;

/**
* This interface defines the API for a subset sum algorithm.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Apr 25, 2016)
*/
public interface SubsetSumFinder {

/**
* Attempts to find a subset of {@code data}, such that all integers in the
* subset sum to {@code sum}.
*
* @param data the list of integers.
* @param sum the requested sum.
* @return a subset summing to {@code sum} or {@code null} if there is no
* such.
*/
public List<Integer> findSubsetWithSum(final List<Integer> data,
final int sum);
}


CombinationIterable.java (already reviewed):



package net.coderodde.combinatorics.support;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

public class CombinationIterable<T> implements Iterable<List<T>> {

private final List<T> allElements;

public CombinationIterable(List<T> allElements) {
this.allElements = new ArrayList<>(allElements);
}

@Override
public Iterator<List<T>> iterator() {
return new CombinationIterator<>(allElements);
}

private static final class CombinationIterator<T>
implements Iterator<List<T>> {

private final List<T> allElements;
private final int indices;
private List<T> nextCombination;
private int currentCombinationSize;

CombinationIterator(List<T> allElements) {
this.allElements = new ArrayList<>(allElements);
this.indices = new int[allElements.size()];

if (!allElements.isEmpty()) {
// Create the first combination.
currentCombinationSize = 1;
nextCombination = new ArrayList<>(1);
nextCombination.add(allElements.get(0));
}
}

@Override
public boolean hasNext() {
return nextCombination != null;
}

@Override
public List<T> next() {
if (nextCombination == null) {
throw new NoSuchElementException("No combinations left.");
}

List<T> combination = nextCombination;
generateNextCombination();
return combination;
}

private void loadCombination() {
List<T> combination = new ArrayList<>(currentCombinationSize);

for (int i = 0; i < currentCombinationSize; ++i) {
combination.add(allElements.get(indices[i]));
}

this.nextCombination = combination;
}

private void generateNextCombination() {
if (indices[currentCombinationSize - 1] < indices.length - 1) {
indices[currentCombinationSize - 1]++;
loadCombination();
return;
}

for (int i = currentCombinationSize - 2; i >= 0; --i) {
if (indices[i] < indices[i + 1] - 1) {
indices[i]++;

for (int j = i + 1; j < currentCombinationSize; ++j) {
indices[j] = indices[j - 1] + 1;
}

loadCombination();
return;
}
}

++currentCombinationSize;

if (currentCombinationSize > indices.length) {
this.nextCombination = null;
return;
}

for (int i = 0; i < currentCombinationSize; ++i) {
indices[i] = i;
}

loadCombination();
}
}
}


FastSubsetSumFinder.java:



package net.coderodde.combinatorics.support;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import net.coderodde.combinatorics.SubsetSumFinder;

/**
* This class implements a faster exact subset sum algorithm.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Apr 25, 2016)
*/
public class FastSubsetSumFinder implements SubsetSumFinder {

@Override
public List<Integer> findSubsetWithSum(List<Integer> data, int sum) {
final List<Integer> list1 = new ArrayList<>();
final List<Integer> list2 = new ArrayList<>();
final int size = data.size();

for (int i = 0; i < size / 2; ++i) {
list1.add(data.get(i));
}

for (int i = size / 2; i < size; ++i) {
list2.add(data.get(i));
}

final List<List<Integer>> combinationList1 = new ArrayList<>();
final List<List<Integer>> combinationList2 = new ArrayList<>();
final Map<List<Integer>, Integer> map = new HashMap<>();

for (final List<Integer> subset : new CombinationIterable<>(list1)) {
map.put(subset, sum(subset));
combinationList1.add(subset);
}

for (final List<Integer> subset : new CombinationIterable<>(list2)) {
map.put(subset, sum(subset));
combinationList2.add(subset);
}

final Comparator<List<Integer>> comparator = new SubsetComparator(map);

Collections.sort(combinationList1, comparator);
Collections.sort(combinationList2, comparator);

int index1 = 0;
int index2 = combinationList2.size() - 1;

while (true) {
int totalSum = map.get(combinationList1.get(index1)) +
map.get(combinationList2.get(index2));

if (totalSum < sum) {
++index1;
} else if (totalSum > sum) {
--index2;
} else {
final List<Integer> solution = new ArrayList<>(size);
solution.addAll(combinationList1.get(index1));
solution.addAll(combinationList2.get(index2));
return solution;
}

if (index1 == combinationList1.size()
|| index2 == -1) {
return null;
}
}
}

private int sum(final List<Integer> subset) {
int sum = 0;

for (final Integer i : subset) {
sum += i;
}

return sum;
}

private static final class SubsetComparator
implements Comparator<List<Integer>> {

private final Map<List<Integer>, Integer> map;

SubsetComparator(final Map<List<Integer>, Integer> map) {
this.map = map;
}

@Override
public int compare(List<Integer> o1, List<Integer> o2) {
final int sum1 = map.get(o1);
final int sum2 = map.get(o2);
return Integer.compare(sum1, sum2);
}
}
}


NaiveSubsetSumFinder.java:



package net.coderodde.combinatorics.support;

import java.util.List;
import net.coderodde.combinatorics.SubsetSumFinder;

/**
* This class implements a naive exact algorithm for solving the subset sum
* problem.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Apr 25, 2016)
*/
public class NaiveSubsetSumFinder implements SubsetSumFinder {

@Override
public List<Integer> findSubsetWithSum(List<Integer> data, int sum) {
final CombinationIterable<Integer> iterable =
new CombinationIterable<>(data);

for (final List<Integer> subset : iterable) {
if (sum(subset) == sum) {
return subset;
}
}

return null;
}

private int sum(final List<Integer> subset) {
int sum = 0;

for (final Integer integer : subset) {
sum += integer;
}

return sum;
}
}


Demo.java:



import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import net.coderodde.combinatorics.SubsetSumFinder;
import net.coderodde.combinatorics.support.FastSubsetSumFinder;
import net.coderodde.combinatorics.support.NaiveSubsetSumFinder;

public class Demo {

private static final int N = 25;
private static final int N_INTEGERS = 100;
private static final int NEEDLE = 1000;

public static void main(final String args) {
final long seed = System.nanoTime();
final Random random = new Random(seed);
final List<Integer> data = new ArrayList<>(N);

System.out.println("Seed = " + seed);

for (int i = 0; i < N; ++i) {
data.add(random.nextInt(N_INTEGERS));
}

final SubsetSumFinder finderNaive = new NaiveSubsetSumFinder();
final SubsetSumFinder finderFast = new FastSubsetSumFinder();

long startTime = System.nanoTime();
final List<Integer> subset1 =
finderNaive.findSubsetWithSum(data, NEEDLE);
long endTime = System.nanoTime();

System.out.printf("NaiveSubsetSumFinder: %5.0f milliseconds. " +
"Result: %s, valid: %b.n",
(endTime - startTime) / 1e6,
subset1,
sum(subset1) == NEEDLE);

startTime = System.nanoTime();
final List<Integer> subset2 =
finderFast.findSubsetWithSum(data, NEEDLE);
endTime = System.nanoTime();

System.out.printf("FastSubsetSumFinder: %5.0f milliseconds. " +
"Result: %s, valid: %b.n",
(endTime - startTime) / 1e6,
subset2,
sum(subset2) == NEEDLE);
}

private static int sum(final List<Integer> subset) {
int sum = 0;

for (final Integer i : subset) {
sum += i;
}

return sum;
}
}


The performance figures are as follows:





NaiveSubsetSumFinder: 3371 milliseconds.
FastSubsetSumFinder: 115 milliseconds.



Any critique much appreciated.










share|improve this question















I have implemented an $mathcal{O}(N2^{N/2})$ algorithm for subset sum problem described in Wikipedia.



That is what I have:



SubsetSumFinder.java:



package net.coderodde.combinatorics;

import java.util.List;

/**
* This interface defines the API for a subset sum algorithm.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Apr 25, 2016)
*/
public interface SubsetSumFinder {

/**
* Attempts to find a subset of {@code data}, such that all integers in the
* subset sum to {@code sum}.
*
* @param data the list of integers.
* @param sum the requested sum.
* @return a subset summing to {@code sum} or {@code null} if there is no
* such.
*/
public List<Integer> findSubsetWithSum(final List<Integer> data,
final int sum);
}


CombinationIterable.java (already reviewed):



package net.coderodde.combinatorics.support;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

public class CombinationIterable<T> implements Iterable<List<T>> {

private final List<T> allElements;

public CombinationIterable(List<T> allElements) {
this.allElements = new ArrayList<>(allElements);
}

@Override
public Iterator<List<T>> iterator() {
return new CombinationIterator<>(allElements);
}

private static final class CombinationIterator<T>
implements Iterator<List<T>> {

private final List<T> allElements;
private final int indices;
private List<T> nextCombination;
private int currentCombinationSize;

CombinationIterator(List<T> allElements) {
this.allElements = new ArrayList<>(allElements);
this.indices = new int[allElements.size()];

if (!allElements.isEmpty()) {
// Create the first combination.
currentCombinationSize = 1;
nextCombination = new ArrayList<>(1);
nextCombination.add(allElements.get(0));
}
}

@Override
public boolean hasNext() {
return nextCombination != null;
}

@Override
public List<T> next() {
if (nextCombination == null) {
throw new NoSuchElementException("No combinations left.");
}

List<T> combination = nextCombination;
generateNextCombination();
return combination;
}

private void loadCombination() {
List<T> combination = new ArrayList<>(currentCombinationSize);

for (int i = 0; i < currentCombinationSize; ++i) {
combination.add(allElements.get(indices[i]));
}

this.nextCombination = combination;
}

private void generateNextCombination() {
if (indices[currentCombinationSize - 1] < indices.length - 1) {
indices[currentCombinationSize - 1]++;
loadCombination();
return;
}

for (int i = currentCombinationSize - 2; i >= 0; --i) {
if (indices[i] < indices[i + 1] - 1) {
indices[i]++;

for (int j = i + 1; j < currentCombinationSize; ++j) {
indices[j] = indices[j - 1] + 1;
}

loadCombination();
return;
}
}

++currentCombinationSize;

if (currentCombinationSize > indices.length) {
this.nextCombination = null;
return;
}

for (int i = 0; i < currentCombinationSize; ++i) {
indices[i] = i;
}

loadCombination();
}
}
}


FastSubsetSumFinder.java:



package net.coderodde.combinatorics.support;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import net.coderodde.combinatorics.SubsetSumFinder;

/**
* This class implements a faster exact subset sum algorithm.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Apr 25, 2016)
*/
public class FastSubsetSumFinder implements SubsetSumFinder {

@Override
public List<Integer> findSubsetWithSum(List<Integer> data, int sum) {
final List<Integer> list1 = new ArrayList<>();
final List<Integer> list2 = new ArrayList<>();
final int size = data.size();

for (int i = 0; i < size / 2; ++i) {
list1.add(data.get(i));
}

for (int i = size / 2; i < size; ++i) {
list2.add(data.get(i));
}

final List<List<Integer>> combinationList1 = new ArrayList<>();
final List<List<Integer>> combinationList2 = new ArrayList<>();
final Map<List<Integer>, Integer> map = new HashMap<>();

for (final List<Integer> subset : new CombinationIterable<>(list1)) {
map.put(subset, sum(subset));
combinationList1.add(subset);
}

for (final List<Integer> subset : new CombinationIterable<>(list2)) {
map.put(subset, sum(subset));
combinationList2.add(subset);
}

final Comparator<List<Integer>> comparator = new SubsetComparator(map);

Collections.sort(combinationList1, comparator);
Collections.sort(combinationList2, comparator);

int index1 = 0;
int index2 = combinationList2.size() - 1;

while (true) {
int totalSum = map.get(combinationList1.get(index1)) +
map.get(combinationList2.get(index2));

if (totalSum < sum) {
++index1;
} else if (totalSum > sum) {
--index2;
} else {
final List<Integer> solution = new ArrayList<>(size);
solution.addAll(combinationList1.get(index1));
solution.addAll(combinationList2.get(index2));
return solution;
}

if (index1 == combinationList1.size()
|| index2 == -1) {
return null;
}
}
}

private int sum(final List<Integer> subset) {
int sum = 0;

for (final Integer i : subset) {
sum += i;
}

return sum;
}

private static final class SubsetComparator
implements Comparator<List<Integer>> {

private final Map<List<Integer>, Integer> map;

SubsetComparator(final Map<List<Integer>, Integer> map) {
this.map = map;
}

@Override
public int compare(List<Integer> o1, List<Integer> o2) {
final int sum1 = map.get(o1);
final int sum2 = map.get(o2);
return Integer.compare(sum1, sum2);
}
}
}


NaiveSubsetSumFinder.java:



package net.coderodde.combinatorics.support;

import java.util.List;
import net.coderodde.combinatorics.SubsetSumFinder;

/**
* This class implements a naive exact algorithm for solving the subset sum
* problem.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Apr 25, 2016)
*/
public class NaiveSubsetSumFinder implements SubsetSumFinder {

@Override
public List<Integer> findSubsetWithSum(List<Integer> data, int sum) {
final CombinationIterable<Integer> iterable =
new CombinationIterable<>(data);

for (final List<Integer> subset : iterable) {
if (sum(subset) == sum) {
return subset;
}
}

return null;
}

private int sum(final List<Integer> subset) {
int sum = 0;

for (final Integer integer : subset) {
sum += integer;
}

return sum;
}
}


Demo.java:



import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import net.coderodde.combinatorics.SubsetSumFinder;
import net.coderodde.combinatorics.support.FastSubsetSumFinder;
import net.coderodde.combinatorics.support.NaiveSubsetSumFinder;

public class Demo {

private static final int N = 25;
private static final int N_INTEGERS = 100;
private static final int NEEDLE = 1000;

public static void main(final String args) {
final long seed = System.nanoTime();
final Random random = new Random(seed);
final List<Integer> data = new ArrayList<>(N);

System.out.println("Seed = " + seed);

for (int i = 0; i < N; ++i) {
data.add(random.nextInt(N_INTEGERS));
}

final SubsetSumFinder finderNaive = new NaiveSubsetSumFinder();
final SubsetSumFinder finderFast = new FastSubsetSumFinder();

long startTime = System.nanoTime();
final List<Integer> subset1 =
finderNaive.findSubsetWithSum(data, NEEDLE);
long endTime = System.nanoTime();

System.out.printf("NaiveSubsetSumFinder: %5.0f milliseconds. " +
"Result: %s, valid: %b.n",
(endTime - startTime) / 1e6,
subset1,
sum(subset1) == NEEDLE);

startTime = System.nanoTime();
final List<Integer> subset2 =
finderFast.findSubsetWithSum(data, NEEDLE);
endTime = System.nanoTime();

System.out.printf("FastSubsetSumFinder: %5.0f milliseconds. " +
"Result: %s, valid: %b.n",
(endTime - startTime) / 1e6,
subset2,
sum(subset2) == NEEDLE);
}

private static int sum(final List<Integer> subset) {
int sum = 0;

for (final Integer i : subset) {
sum += i;
}

return sum;
}
}


The performance figures are as follows:





NaiveSubsetSumFinder: 3371 milliseconds.
FastSubsetSumFinder: 115 milliseconds.



Any critique much appreciated.







java algorithm






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Apr 25 '16 at 9:49









Mast

7,43963686




7,43963686










asked Apr 25 '16 at 9:44









coderodde

15.6k536121




15.6k536121












  • I can see from your numbers that Fast is actually faster than naive, but your perf testing technique is flawed. Java heavily optimises code as it executes, so you need to run through your code quite a lot to allow the jvm to complete doing that before you start measuring performance.
    – Engineer Dollery
    Apr 27 '16 at 14:53










  • Yeah, I know: the warmup effect. In case you don't trust the figures, roll your own warmup code (I am not sure whether it is O.K. to edit the question). However, I am confident that the Fast implementation has better time complexity.
    – coderodde
    Apr 27 '16 at 14:56


















  • I can see from your numbers that Fast is actually faster than naive, but your perf testing technique is flawed. Java heavily optimises code as it executes, so you need to run through your code quite a lot to allow the jvm to complete doing that before you start measuring performance.
    – Engineer Dollery
    Apr 27 '16 at 14:53










  • Yeah, I know: the warmup effect. In case you don't trust the figures, roll your own warmup code (I am not sure whether it is O.K. to edit the question). However, I am confident that the Fast implementation has better time complexity.
    – coderodde
    Apr 27 '16 at 14:56
















I can see from your numbers that Fast is actually faster than naive, but your perf testing technique is flawed. Java heavily optimises code as it executes, so you need to run through your code quite a lot to allow the jvm to complete doing that before you start measuring performance.
– Engineer Dollery
Apr 27 '16 at 14:53




I can see from your numbers that Fast is actually faster than naive, but your perf testing technique is flawed. Java heavily optimises code as it executes, so you need to run through your code quite a lot to allow the jvm to complete doing that before you start measuring performance.
– Engineer Dollery
Apr 27 '16 at 14:53












Yeah, I know: the warmup effect. In case you don't trust the figures, roll your own warmup code (I am not sure whether it is O.K. to edit the question). However, I am confident that the Fast implementation has better time complexity.
– coderodde
Apr 27 '16 at 14:56




Yeah, I know: the warmup effect. In case you don't trust the figures, roll your own warmup code (I am not sure whether it is O.K. to edit the question). However, I am confident that the Fast implementation has better time complexity.
– coderodde
Apr 27 '16 at 14:56










1 Answer
1






active

oldest

votes

















up vote
0
down vote













Naive works with following but fast does not.
data = "1,3,8,10,20"
answer = 18






share|improve this answer








New contributor




Don Rau is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.


















    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ifUsing("editor", function () {
    StackExchange.using("externalEditor", function () {
    StackExchange.using("snippets", function () {
    StackExchange.snippets.init();
    });
    });
    }, "code-snippets");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "196"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    convertImagesToLinks: false,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f126624%2ffast-exact-algorithm-for-subset-sum-problem-in-java%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    0
    down vote













    Naive works with following but fast does not.
    data = "1,3,8,10,20"
    answer = 18






    share|improve this answer








    New contributor




    Don Rau is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.






















      up vote
      0
      down vote













      Naive works with following but fast does not.
      data = "1,3,8,10,20"
      answer = 18






      share|improve this answer








      New contributor




      Don Rau is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.




















        up vote
        0
        down vote










        up vote
        0
        down vote









        Naive works with following but fast does not.
        data = "1,3,8,10,20"
        answer = 18






        share|improve this answer








        New contributor




        Don Rau is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.









        Naive works with following but fast does not.
        data = "1,3,8,10,20"
        answer = 18







        share|improve this answer








        New contributor




        Don Rau is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.









        share|improve this answer



        share|improve this answer






        New contributor




        Don Rau is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.









        answered 14 mins ago









        Don Rau

        1




        1




        New contributor




        Don Rau is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.





        New contributor





        Don Rau is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.






        Don Rau is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to Code Review Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.





            Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


            Please pay close attention to the following guidance:


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f126624%2ffast-exact-algorithm-for-subset-sum-problem-in-java%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            404 Error Contact Form 7 ajax form submitting

            How to know if a Active Directory user can login interactively

            TypeError: fit_transform() missing 1 required positional argument: 'X'