# Getting permutations of a set

I'd like some feedback on my implementation to get all the permutations of a set.

Eg:

@Test
public void test()
{
def data = [["A","B"],["A","B","C","D"],["D","E","F"]]
def expected = toResultSet("ABD,ABE,ABF,ACD,ACE,ACF,ADE,ADF,BAD,BAE,BAF,BCD,BCE,BCF,BDE,BDF");
def result = SetPermutations.getSetPermutations(data);
assert result.containsAll(expected);
assert result.size() == expected.size();
}


Note that:

• The input is a collection of collections
• Each collection may have a different number of items
• Each item may appear in more than 1 collection (in the input) (ie., data and data both contain "A")
• Each resulting permutation must contain exactly 1 item from each of the input sets
• Each item may only appear once in a given permutation (ie., 'AAB' is invalid)

Here is my implementation: (Note, my test is in groovy, but the implementation is java)

public class SetPermutations<E> {

private List<E> permutationSet;
private final Collection<Collection<E>> input;
private final int maxDepth;
private final Set<List<E>> result;

public static <E> Set<List<E>> getSetPermutations(Collection<Collection<E>> input)
{
SetPermutations<E> setPermutations = new SetPermutations<E>(input);
return setPermutations.build();
}

private SetPermutations(Collection<Collection<E>> input)
{
this.input = input;
maxDepth = input.size() - 1;
result = new HashSet<List<E>>();
}

private Set<List<E>> build() {
List<Collection<E>> list = new ArrayList<Collection<E>>(input);

int currentDepth = 0;
permutationSet = newPermutationSet();

permute(list,currentDepth);

return result;
}
private void permute(List<Collection<E>> list,
int currentDepth) {
Collection<E> collection = list.get(currentDepth);
for (E object : collection) {
if (permutationSet.contains(object))
continue;

permutationSet.add(object);

if (currentDepth != maxDepth)
{
permute(list, currentDepth + 1);
permutationSet.remove(object);
} else {
result.add(permutationSet);
// Allow the recursion to continue on a new permutationSet,
// but remove our item from it.
permutationSet = clonedPermutationSet();
permutationSet.remove(object);
}
}
}

private List<E> newPermutationSet() {
return new ArrayList<E>();
}
private List<E> clonedPermutationSet() {
return new ArrayList<E>(permutationSet);
}
}


I have a few specific questions:

• Am I reinventing the wheel here? I searched, and couldn't find a suitable implementation for this problem anywhere, but I find it hard to believe that this hasn't been solved before (better than my solution)
• Is there a better way for me to have implemented this?
• Are you deliberately using Collection<Object>, or is this something that should be handled by making the collections generic? – Clockwork-Muse Jan 24 '12 at 18:43
• Great idea -- no specific reason, I've just tweaked it to use Generics. – Marty Pitt Jan 24 '12 at 19:58
• I've updated the post to show the generics version - feedback greatly appreciated. – Marty Pitt Jan 24 '12 at 20:03

## 1 Answer

There's a number of things going on here, but the first thing that comes to mind is that you're placing an object on the heap that you simply discard (the entire class) for no apparent reason (speaking logically, not in terms of objects created). Given that you don't appear to keep the object at all, this is unnecessary - do this all with static methods. Additionally, this is not threadsafe, and the basic design cannot be adjusted to execute on multiple threads. Furthermore, you're returning a Set<List<E>>, but your results are logically Set<Set<E>> (because you don't have repeats) - You probably ought to either adjust your results, or change your return results.

There's also a compile error in your code since you switched to the generics version, because of type inference (and this took me a while to figure out).

Most of the disconnect is occurring because of the odd blend of static and instance methods. Additionally, you're attempting to use a builder pattern for something that doesn't really call for it - as near as the caller of your method knows, your SetPermutations class is never instantiated (which is false). Also, you add object to permutationSet... and then almost immediately remove it. Regardless of the performance implications of that, it's a terrible thing to do to a developer's mind.

Here's my (intial) take on the issue. Note that this version is threadsafe (so long as T is an immutable object), and amenable to (easier) threading. There are a few areas that could maybe be tweaked, especially as I'm creating a few more objects than I actually need (notably, my termination condition in permute), but this should be a better starting place.

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public abstract class SetPermutations {

private SetPermutations() {
// no state.
}

public static <T> Set<Set<T>> getSetPermutations(final Collection<? extends Collection<T>> input) {
if (input == null) {
throw new IllegalArgumentException("Input not provided!");
}
final List<Set<T>> saved = new ArrayList<Set<T>>();
for (Collection<T> c : input) {
Set<T> s = new HashSet<T>(c);
c.remove(null);
if (c.size() >= 1) {
saved.add(s);
} else {
throw new IllegalArgumentException("Input includes null/empty collection!");
}
}

return permute(new HashSet<T>(), saved);
}

private static <T> Set<Set<T>> permute(final Set<T> initial, final List<Set<T>> itemSets) {

if (itemSets.isEmpty()) {
return Collections.singleton(initial);
}

final Set<T> items = itemSets.get(0);
final List<Set<T>> remaining = itemSets.subList(1, itemSets.size());
final int computedSetSize = initial.size() * items.size() * remaining.size();
final Set<Set<T>> computed = new HashSet<Set<T>>(computedSetSize, 1);

for (T item : items) {
if (!initial.contains(item)) {
Set<T> permutation = new HashSet<T>(initial);
permutation.add(item);
computed.addAll(permute(permutation, remaining));
}
}

return computed;
}

}


And here's the (revised) JUnit test to prove behaviour:

@Test
public void setPermutationsTest() {
List<List<String>> data = new ArrayList<List<String>>();
data.add(Arrays.asList("A", "B"));
data.add(Arrays.asList("A","B","C","D"));
data.add(Arrays.asList("D","E"));
Set<Set<String>> expected = new HashSet<Set<String>>();
expected.add(new HashSet<String>(Arrays.asList("A", "B", "D")));
expected.add(new HashSet<String>(Arrays.asList("A", "B", "E")));
expected.add(new HashSet<String>(Arrays.asList("A", "C", "D")));
expected.add(new HashSet<String>(Arrays.asList("A", "C", "E")));
expected.add(new HashSet<String>(Arrays.asList("A", "D", "E")));
expected.add(new HashSet<String>(Arrays.asList("B", "C", "D")));
expected.add(new HashSet<String>(Arrays.asList("B", "C", "E")));
expected.add(new HashSet<String>(Arrays.asList("B", "D", "E")));
Set<Set<String>> result = SetPermutations.<String>getSetPermutations(data);
assertTrue(result.containsAll(expected));
assertTrue(result.size() == expected.size());
}


(I removed "F" from the last collection, as it wasn't adding anything in terms of conditions - it fufilled the same function as "E").

EDIT:

The main reason why this is (more, and as much as can be reasonably coded for) threadsafe is the fact that you're not (completely) operating on a 'saved' copy:

1. You save off maxDepth before copying the 'exterior' collection. If the size of that collection changes, maxDepth's value is now incorrect (results undefined).
2. You copy (and work from) the 'exterior' collection, but don't copy the 'interior' collections (The copy constructors might be deep for existing collections, but I doubt it, and won't be for custom collections). This means that if any of the interior collections are modified during process run, you won't get correct results.

As for the static method instantiating a version of itself - there's no problem with that. In fact, that generally forms the basis of a Factory Pattern. The catch is that the instantiation is being returned - that is, the desired result is the instantiation. Here, the only result is that you end up with a confusing use of instance variables. The permutationSet methods end up being unwanted noise (It would have been better to explicitly just use the constructors), and are misleading to boot (you're returning a LIST). Additionally, because of the use of the instance variables, it becomes non-trivial to reason about the state of the various collections. NONE of the work done by instance methods benefits significantly from working on instance variables. The only (theorhetical) benefit gained is that you work with a single copy of a result HashSet (because I define intermediate ones) - however, if it's an issue, the necessary collection should be passed in (as in a load() method.
Also, by permorming the instantiation as you have, you've completely eliminated any potential hope of threading the process (a potential concern, given that this is basically an O(n ^ m) process, where n is the number of collections, and m is the size of the collections, assuming roughly equal collection sizes). With a thread pool and using futures, a non-instantiated version (or at least, not instantiated like this) can be threaded fairly trivially.

• Thanks for this - I appreciate the feedback. I'll need to step through the code to fully grok it. However, would you mind expanding on why this is more threadsafe than the original? Additionally, I'm interested to know why you believe it's bad for a static method to instantiate a version of itself -- ie., why should the caller care about the internals of how the invocation works? – Marty Pitt Jan 25 '12 at 0:14