Combination Java Performance

Question

I want to use this function with a large amount of possibility like 700 integer but the function make too much time to execute. Does someone have an idea to increase the performance? Thank you :)

public static Set<Set<Integer>> combinations(List<Integer> groupSize, int k) {

    Set<Set<Integer>> allCombos = new HashSet<Set<Integer>> ();
    // base cases for recursion
    if (k == 0) {
        // There is only one combination of size 0, the empty team.
        allCombos.add(new HashSet<Integer>());
        return allCombos;
    }
    if (k > groupSize.size()) {
        // There can be no teams with size larger than the group size,
        // so return allCombos without putting any teams in it.
        return allCombos;
    }

    // Create a copy of the group with one item removed.
    List<Integer> groupWithoutX = new ArrayList<Integer> (groupSize);
    Integer x = groupWithoutX.remove(groupWithoutX.size() - 1);

    Set<Set<Integer>> combosWithoutX = combinations(groupWithoutX, k);
    Set<Set<Integer>> combosWithX = combinations(groupWithoutX, k - 1);
    for (Set<Integer> combo : combosWithX) {
        combo.add(x);
    }
    allCombos.addAll(combosWithoutX);
    allCombos.addAll(combosWithX);
    return allCombos;
}

You can't really obtain all the combinations in a faster time than ``n!`` — Schidu Luca, Oct 23 '17 at 10:17
Have you tried breaking the steps down by setting break points to may detect **which action(s) exactly** take "too long" to execute? (using a stop watch) — Filnor, Oct 23 '17 at 10:18
I don't see easy solution in Java (Scala would help a lot). You may find interesting this post: https://stackoverflow.com/questions/3515739/parallel-programming-with-recursive-functions — marco, Oct 23 '17 at 11:27

OldCurmudgeon · Answer 1 · 2017-10-23T14:20:18.880

1

What features of Set are you going to need to use on the returned value?

If you only need some of them - perhaps just iterator() or contains(...) - then you could consider returning an Iterator which calculates the combinations on the fly.

There's an interesting mechanism to generate the nth combination of a lexicographically ordered set here.

edited Oct 23 '17 at 14:20

answered Oct 23 '17 at 12:21

OldCurmudgeon

64,482
16
119
213

score 0 · Answer 2 · answered Oct 23 '17 at 10:40

Other data structure. You could try a BitSet instead of the Set<Integer>. If the integer values have a wild range (negative, larger gaps), use an index in groupSize.

Using indices instead of integer values has other advantages: all subsets as bits can be done in a for-loop (BigInteger as set).

No data. Or make an iterator (Stream) of all combinations to repeatedly apply to your processing methods.

Concurrency. Paralellism would would only mean a factor 4/8. ThreadPoolExecutor and Future maybe.

OPTIMIZING THE ALGORITHM ITSELF

The set of sets could better be a List. That tremendously improves adding a set. And shows whether the algorithm does not erroneously create identical sets.

Combination Java Performance

2 Answers2