2
\$\begingroup\$

Let's assume I have a one-dimensional array of integers of size n. My problem is to generate all the combination of all possible groups of size 1 to n, such as each combination has exactly one occurrence of each element. The order does not count:

[[1,2]] == [[2,1]]
[[1],[2]] == [[2],[1]]
[[1,2],[3,4]] == [[2,1],[4,3]] == [[4,3],[2,1]]...

For example, for the input array [1,2], I would get:

[[1,2]]
[[1],[2]]

With [1,2,3], I would have:

[[1,2,3]]
[[1,2],[3]]
[[1,3],[2]]
[[2,3],[1]]
[[1],[2],[3]]

And with [1,2,3,4]:

[[1,2,3,4]]
[[1,2,3],[4]]
[[1,2,4],[3]]
[[1,3,4],[2]]
[[2,3,4],[1]]
[[1,2],[3,4]] <= Equivalent to [[3,4],[1,2]]
[[1,3],[2,4]] <= Equivalent to [[2,4],[1,3]]
[[1,4],[2,3]] <= Equivalent to [[2,3],[1,4]]
[[1,2],[3],[4]]
[[1,3],[2],[4]]
[[1,4],[2],[3]]
[[2,3],[1],[4]]
[[2,4],[1],[3]]
[[3,4],[1],[2]]
[[1],[2],[3],[4]]

My code below is working but is actually very slow when the list has more than 6 elements:

public Set<Set<Set<Integer>>> recurseGroups(List<Integer> initialArray, List<Set<Integer>> currentGroups, int i) {
    if (i == initialArray.size()) {
        // Deep copy current group to save its content
        Set<Set<Integer>> copy = currentGroups.stream()
                .map(HashSet::new)
                .collect(Collectors.toSet());

        return Collections.singleton(copy);
    }

    Set<Set<Set<Integer>>> result = new HashSet<>();

    for (int j = i; j < initialArray.size(); ++j) {
        // Add a singleton group with the i-th integer
        // And generate groups with the remaining elements
        Set<Integer> newGroup = new HashSet<>(Collections.singletonList(initialArray.get(i)));
        currentGroups.add(newGroup);
        result.addAll(recurseGroups(initialArray, currentGroups, i + 1));
        currentGroups.remove(newGroup);

        // Add the i-th integer to each previous existing groups
        // And generate groups with the remaining elements
        for (int k = 0; k < currentGroups.size(); ++k) {
            currentGroups.get(k).add(initialArray.get(i));
            result.addAll(recurseGroups(initialArray, currentGroups, i + 1));
            currentGroups.get(k).remove(initialArray.get(i));
        }
    }

    return result;
}

// Calling line
Set<Set<Set<Integer>>> groups = recurseGroups(Arrays.asList(1,2,3), new ArrayList<>(), 0)

By adding a log in the stop condition, I noticed the code actually adds many times the same group combinations. I suspect it would be possible to improve the stop condition or the loop, but I don't see how.

\$\endgroup\$
  • \$\begingroup\$ Why are you writing this code? I have a feeling this is not some homework, and not something you do just for fun. What is the real reason behind this? \$\endgroup\$ – Simon Forsberg Jul 24 '17 at 16:54
  • \$\begingroup\$ This is indeed not homework. It's for a side project of mine, so kinda for fun! I need this algo for an huge optimization of my code. Well, I think so. The big picture is a bit more complicated but overall, it boils down to this. \$\endgroup\$ – bill0ute Jul 24 '17 at 17:05
  • \$\begingroup\$ I believe these are partitions and not combinations. \$\endgroup\$ – coderodde Jul 24 '17 at 17:11
  • \$\begingroup\$ The reason for my question is partially because I've written a Minesweeper game with a lot of analysis to it, so I find the subject interesting. I also think that explaining some of the context would make your question better and would make it easier to help you. See Simon's Guide to posting a good question. Additionally, I am wondering if you have to keep a reference to the result, or if you can iterate through them when they appear? \$\endgroup\$ – Simon Forsberg Jul 24 '17 at 17:11
  • \$\begingroup\$ @coderodde you are absolutely right! Knowing the name of what your are looking for is sometimes helpful... Their are actually quite few posts on that on StackOverFlow: here or here \$\endgroup\$ – bill0ute Jul 24 '17 at 17:57
2
\$\begingroup\$

After spending more hours than I'd like to admit on trying to figure out your algorithm and why it is slow, and after multiple false epiphanies, thinking that I have finally discovered the weakness in your program, I believe that, now, I have really found out where the problem with your code lies. Considering all the drafts I've written for explaining where your algorithms wastes performances, trying to format it so that it is easy to read, and even trying out some LaTeX expressions, the emphasis on the word "painfully" becomes all the more justified when I say that the explanation for your algorithm's unsatisfactory performance is really painfully simple. So here goes … the reason your code is slow is:

$$...$$
$$...$$
$$j$$
Seriously, when the for loop that introduces int j is executed after the first time, it does nothing it hasn't already done the first time around. All local variables declared outside the loop except result (i.e. the method parameters) have the exact same values as they did during the first execution of the loop. I can't believe I didn't see this earlier.

But now that I'm writing an answer to this question, I will also tell you what I did to make the code a bit more read-/understandable (in my opinion). Since, inside the method body, only elements from initialArray with an index larger than or equal to i are queried, and i doesn't serve any other purpose than to mark this index, I've eliminated i altogether and adjusted the recursive calls so that they only pass a sublist of the array with the relevant elements:

public Set<Set<Set<Integer>>> recurseGroups(List<Integer> integerList, List<Set<Integer>> currentGroups) {
    if (integerList.isEmpty()) {
        // ...
    }

    for (int j = 0; j < integerList.size(); ++j) {
        // ...
        Set<Integer> newGroup = new HashSet<>(Collections.singletonList(integerList.get(0)));
        currentGroups.add(newGroup);
        result.addAll(recurseGroups(integerList.subList(1, integerList.size()), currentGroups));
        currentGroups.remove(newGroup);

        // ...
        for (int k = 0; k < currentGroups.size(); ++k) {
            currentGroups.get(k).add(integerList.get(0));
            result.addAll(recurseGroups(integerList.subList(1, integerList.size()), currentGroups));
            currentGroups.get(k).remove(integerList.get(0));
        }
    }

    // ...
}

That way, no information that isn't needed enters the method, which makes it easier to understand its workings.

Also, the following line is really unnecessarily complicated:

Set<Integer> newGroup = new HashSet<>(Collections.singletonList(integerList.get(0)));

This creates a List that is never used again and serves no other purpose than to save one line of code. You might as well do this:

Set<Integer> newGroup = new HashSet<>();
newGroup.add(integerList.get(0));

Even with two lines, it still takes up less characters than the above version, and it doesn't do more than it needs to do, hence easier to read.

That's it, now I really have to go to sleep. Happy coding!

\$\endgroup\$
1
\$\begingroup\$

Thanks for sharing the code.

It really looks nice and clean but it focuses on handling of the data structure rather than on individual objects.

I'd look at this way:

I get unique groups if I only group with the values to the right:

 input [1,2,3,4]
 pick 1
 call pairing(1,[2,3,4]) -> [1,2][1,3][1,4]
 pick 2
 call pairing(2,[3,4]) -> [2,3][2,4] // but not [2,1]!

With this approach, would the result [[1,3,4],[2]] ever appear? – Simon Forsberg

Maybe we have to change the point of view. We usually look for constructive solutions, but maybe a destructive approach is more suitable:

 input [1,2,3,4]
 pick 1
 takeout( 1, [1,2,3,4])-> [1][2,3,4]
 pick 2
 takeout (2, [1,2,3,4]) -> [2][1,3,4]
 pick 1
   goup(1,[2,3,4])->
       takeout([1,2],[1,2,3,4])->[1,2][3,4]
       takeout([1,3],[1,2,3,4])->[1,3][2,4]
       takeout([1,4],[1,2,3,4])->[1,4][2,3]
       goup([1,2],[3,4])
          takeout([1,2,3],[1,2,3,4])-> [1,2,3][4]
 // ...

To avoid duplication of [1,2,3][4] and [4][1,2,3] we should stop the iteration at n/2...

\$\endgroup\$
  • \$\begingroup\$ With this approach, would the result [[1,3,4],[2]] ever appear? \$\endgroup\$ – Simon Forsberg Jul 24 '17 at 17:13
  • \$\begingroup\$ @SimonForsberg this completely depends on the implementation... ;o) \$\endgroup\$ – Timothy Truckle Jul 24 '17 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.