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.
java algorithm
edited Apr 25 '16 at 9:49
Mast
7,43963686
asked Apr 25 '16 at 9:44
coderodde
15.6k536123
add a comment |
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.
java algorithm
edited Apr 25 '16 at 9:49
Mast
7,43963686
asked Apr 25 '16 at 9:44
coderodde
15.6k536123
1
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 theFastimplementation has better time complexity.
– coderodde
Apr 27 '16 at 14:56
add a comment |
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.
java algorithm
edited Apr 25 '16 at 9:49
Mast
7,43963686
asked Apr 25 '16 at 9:44
coderodde
15.6k536123
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
java algorithm
edited Apr 25 '16 at 9:49
Mast
7,43963686
asked Apr 25 '16 at 9:44
coderodde
15.6k536123
edited Apr 25 '16 at 9:49
Mast
7,43963686
asked Apr 25 '16 at 9:44
coderodde
15.6k536123
edited Apr 25 '16 at 9:49
Mast
7,43963686
edited Apr 25 '16 at 9:49
Mast
7,43963686
edited Apr 25 '16 at 9:49
Mast
7,43963686
7,43963686
asked Apr 25 '16 at 9:44
coderodde
15.6k536123
asked Apr 25 '16 at 9:44
coderodde
15.6k536123
asked Apr 25 '16 at 9:44
coderodde
15.6k536123
15.6k536123
1
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 theFastimplementation has better time complexity.
– coderodde
Apr 27 '16 at 14:56
add a comment |
1
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 theFastimplementation has better time complexity.
– coderodde
Apr 27 '16 at 14:56
1
1
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
add a comment |
1 Answer
1
active
oldest
votes
up vote
3
down vote
I found a case that needs some attention.
The naive version works with following, but the fast version does not:
- data = "1,3,8,10,20"
- answer = 18
edited Dec 6 at 8:43
Toby Speight
23.2k638110
answered Dec 6 at 3:49
Don Rau
312
Can you help the OP fix it?
– Null
Dec 6 at 4:47
add a comment |
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
3
down vote
I found a case that needs some attention.
The naive version works with following, but the fast version does not:
- data = "1,3,8,10,20"
- answer = 18
edited Dec 6 at 8:43
Toby Speight
23.2k638110
answered Dec 6 at 3:49
Don Rau
312
Can you help the OP fix it?
– Null
Dec 6 at 4:47
add a comment |
up vote
3
down vote
I found a case that needs some attention.
The naive version works with following, but the fast version does not:
- data = "1,3,8,10,20"
- answer = 18
edited Dec 6 at 8:43
Toby Speight
23.2k638110
answered Dec 6 at 3:49
Don Rau
312
Can you help the OP fix it?
– Null
Dec 6 at 4:47
add a comment |
up vote
3
down vote
up vote
3
down vote
I found a case that needs some attention.
The naive version works with following, but the fast version does not:
- data = "1,3,8,10,20"
- answer = 18
edited Dec 6 at 8:43
Toby Speight
23.2k638110
answered Dec 6 at 3:49
Don Rau
312
I found a case that needs some attention.
The naive version works with following, but the fast version does not:
- data = "1,3,8,10,20"
- answer = 18
edited Dec 6 at 8:43
Toby Speight
23.2k638110
answered Dec 6 at 3:49
Don Rau
312
edited Dec 6 at 8:43
Toby Speight
23.2k638110
edited Dec 6 at 8:43
Toby Speight
23.2k638110
edited Dec 6 at 8:43
Toby Speight
23.2k638110
23.2k638110
answered Dec 6 at 3:49
Don Rau
312
answered Dec 6 at 3:49
Don Rau
312
answered Dec 6 at 3:49
Don Rau
312
312
Can you help the OP fix it?
– Null
Dec 6 at 4:47
add a comment |
Can you help the OP fix it?
– Null
Dec 6 at 4:47
Can you help the OP fix it?
– Null
Dec 6 at 4:47
Can you help the OP fix it?
– Null
Dec 6 at 4:47
add a comment |
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
1
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
Fastimplementation has better time complexity.– coderodde
Apr 27 '16 at 14:56