Permutation of n lists

I have code which gives permutations for 10 lists. The code works fine for small number of lists with small number of values.

Result : It should return all possible permutations. I have to store the permutations instead of directly working on it and discarding.

As soon as I try for 10 lists, it errors out with OOM : heap space.

Can one of you suggest optimizations for this piece of code?

```
public static Collection> permutations(List> collections) {
if (collections == null || collections.isEmpty()) {
return Collections.emptyList();
} else {
Collection> result = Lists.newLinkedList();
findPermutations(collections, result, 0, new LinkedList());
return result;
}
}

private static void findPermutations(List> inputList, Collection> outputList, int d, List tempList) {
if (d == inputList.size()) {
outputList.add(tempList);
return;
}

Collection currentCollection = inputList.get(d);
for (T currElement : currentCollection) {
List copy = Lists.newLinkedList(tempList);
copy.add(currElement);
findPermutations(inputList, outputList, d + 1, copy);
}
}

@SuppressWarnings("unchecked")
public static void main(String[] args) {

List list1 = Lists.newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 0);
List list2 = Lists.newArrayList("a", "s", "d", "f", "g", "h", "j", "k", "l", "m", "n", "b");
List list3 = Lists.newArrayList(true, false, true, true, true);
List list4 = Lists.newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 0);
List list5 = Lists.newArrayList("a", "s", "d", "f", "g", "h", "j", "k", "l", "m", "n", "b");
List list6 = Lists.newArrayList(true, false, true, true, true);
List list7 = Lists.newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 0);
List list8 = Lists.newArrayList("a", "s", "d", "f", "g", "h", "j", "k", "l", "m", "n", "b");
List list9 = Lists.newArrayList(true, false, true, true, true);
List list10 = Lists.newArrayList(true, false, true, true, t

When writing programs it is often important to do some mental math before you start. In Math class at school they would often suggest that you estimate what the answer will be to a problem before you calculate it "for real".

Here, what you have, is a recursive function. Each time the function is called, it loops over the current-list's members creates a new LinkedList, adds the member and then recurses.

The algorithm is actually quite clean, and readable.... but, do the math:

For a list of 10 members, you create 10 "sub" lists. For each of those sub lists, you recurse, and create 10 more..... so, taking your example of 10 lists of 5 members, how big will your results be (how many lists....)?

5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5

9765625, but let's call that 10 million

Now, each list is a LinkedList which creates a Node instance for each member, so, each LinkedList has 6 instances created to store references to the members (and the list itself), so, let's just say that each instance is 32 bytes (which is about right - by the way).... that's

10Meg * 6 * 32

That's 1.92 Gig

Now, you take in to account various other things, like the fact that you are storing each list in another list, which will need 10 million members of 32-bytes.... or 320 meg, you are past the 2Gig mark.

So, your solution will use "more than" 2 Gig for your 10-lists of 5-members.

How can you support 10-by-10 solutions? (10 billion permutations - 1000 times more than 10-by-5)..... I don't believe you can....

What you can do though, is be more memory efficient with your data structures....

Using an ArrayList instead of a Linked List will reduce your per-node memory from 32bytes-per-node to just 8 or so.....

Using an iterator/push mechanism will remove the need for the list entirely, and will not need to store anything at all.....

Otherwise, frankly, you're out of luck.... there's just no way that you can create a scalable system that has a size-complexity of \$O(m^n)\$ where m is the number of elements in each list, and n is the number of lists....

For example, in your code, you can remove the results list entirely, and then simply replace the lines:

if (d == inputList.size()) {
    outputList.add(tempList);
    return;
}

with:

if (d == inputList.size()) {
    System.out.println(tempList);
    return;
}

And suddenly you will no longer be constrained by memory (though it will be pretty damn slow still).

StackExchange Code Review Q#91475, answer score: 8