4
\$\begingroup\$

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 <T> Collection<List<T>> permutations(List<Collection<T>> collections) {
    if (collections == null || collections.isEmpty()) {
        return Collections.emptyList();
    } else {
        Collection<List<T>> result = Lists.newLinkedList();
        findPermutations(collections, result, 0, new LinkedList<T>());
        return result;
    }
}

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

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

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

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

    long currentTime1 = System.currentTimeMillis();

    List<Collection<T>> finalList = Lists.newArrayList();
    finalList.add((Collection<T>) list2);
    finalList.add((Collection<T>) list1);
    finalList.add((Collection<T>) list3);
    finalList.add((Collection<T>) list4);
    finalList.add((Collection<T>) list5);
    finalList.add((Collection<T>) list6);
    finalList.add((Collection<T>) list7);
    finalList.add((Collection<T>) list8);
    finalList.add((Collection<T>) list9);
    finalList.add((Collection<T>) list10);

    Collection<List<T>> resultList = permutations(finalList);

    long currentTime2 = System.currentTimeMillis();

    long timeTaken = (currentTime2 - currentTime1);

    System.out.println("result is : " + resultList + "\n" + "size is : " + resultList.size() + "\n" + "time taken is : " + timeTaken);

}
\$\endgroup\$
5
  • \$\begingroup\$ Even 10 lists of 5 values each is throwing heap space error \$\endgroup\$ – Ravi Agarwal May 22 '15 at 8:57
  • \$\begingroup\$ What do you mean by "permutation" exactly? \$\endgroup\$ – Ben Aaronson May 22 '15 at 9:03
  • \$\begingroup\$ It should print all the combinations like {1,a,true,1,a,true,1,a,true,true}, {1,a,true,1,a,true,1,a,true,false}, ...... The order matters so {a,b} and {b,a} are essentially 2 different sets in the result \$\endgroup\$ – Ravi Agarwal May 22 '15 at 9:20
  • \$\begingroup\$ Can you remove duplicates from each list? The true/false lists have repeated elements. \$\endgroup\$ – JS1 May 22 '15 at 14:56
  • \$\begingroup\$ the lists will not have duplicate elements. I added them just to mimic data and try out different datatypes. \$\endgroup\$ – Ravi Agarwal May 22 '15 at 15:14
2
\$\begingroup\$

If you are receiving an OutOfMemoryError, you'll have to get a PC with 64bit VM, 32GB of RAM, and start your program with

java -Xmx30g YourProgram

giving it 30 GB of memory to fill.


But seriously: Although you explicitly said so, I doubt that you have to store the permutations, always, for all the time. As rolfl already pointed out, you'll quickly run out of memory in any case. And even if you manage to squeeze the result into your current memory: Increasing the number of lists by 1, or increasing the size of each list by 1, will cause an exponential growth of the result, and you'll be back at the OutOfMemoryError again.


First a short side note: You can avoid these ugly cases of the lists to Collection<T>. Your permutation computing methods to not actually need the specific types (and since the resulting list contains mixed types, the parameter T will fall back to be Object anyhow). By changing the signature of your methods to

public static <T> Collection<List<T>> permutations(
    List<? extends Collection<? extends T>> collections) { ... }

private static <T> void findPermutations(
    List<? extends Collection<? extends T>> inputList, ...) { ... }

and the single local collection to

Collection<? extends T> currentCollection = inputList.get(d);

you can omit all casts, and declare your input as

List<Collection<?>> finalList = new ArrayList<>();
finalList.add(list2);
finalList.add(list1);
...

Back to your memory issue: It seems unlikely that you really need all the result lists in memory all the time. Unless you really want to do random access on the resulting list of lists, you can avoid storing these lists explicitly: If you only want to iterate over the resulting lists, then you can create an Iterable that computes the combinations on the fly. You can find such an iterable at https://github.com/javagl/Combinatorics/blob/master/src/main/java/de/javagl/utils/math/combinatorics/MixedRangeCombinationIterable.java (it's self-contained, you can simply copy & paste this single class into your project).

With this, instead of computing the resultList with your current permutation method, you can simply create an Iterable that allows you to iterate over all elements of the resulting combinations like this:

MixedRangeCombinationIterable<Object> results = 
    new MixedRangeCombinationIterable<Object>(finalList);
for (List<Object> result : results)
{
    System.out.println(result);
}
\$\endgroup\$
2
  • \$\begingroup\$ Thanks @Marco13.. Your answer is really helpful. I think using iterable will probably solve my case here. Its my bad that I did not think of using Iterable earlier! \$\endgroup\$ – Ravi Agarwal May 22 '15 at 15:17
  • \$\begingroup\$ @RaviAgarwal A side note: You are basically iterating over the elements of the Cartesian Product of your input lists. See en.wikipedia.org/wiki/Cartesian_product \$\endgroup\$ – Marco13 May 22 '15 at 15:18
8
\$\begingroup\$

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).

\$\endgroup\$
1
  • \$\begingroup\$ Thanks rolfl. I agree with everything that you said and will be trying out using Iterable for this in my project. Also, I had changed the code to avoid using linked list but somehow pasted the old code here! Thanks for that suggestion too. \$\endgroup\$ – Ravi Agarwal May 22 '15 at 15:19
1
\$\begingroup\$

To expand on Rofl's point about efficient data structures, the most efficient data structure in terms of space is code, and currently this is a space constrained problem.

Values

The set of all permutations P of a collection of lists C is a constant value, not a procedure or function. This means that there are really only two ways it can be used:

  1. We can compare another value to P. This would be a search operation. Note that this is distinct from comparison to C.
  2. We can perform an operation on it mapping it to a new value [possibly, we could map with the identity function]. This would be an iteration.

Search

This is basically the case where we have a value x and want to know if x is a member of P. Since P is a permutation, x must be a tuple. The comparison can boils down to:

 Loop i = 0
     If i = C.length
        return TRUE
     Else
        If C[i].member(x[i])
            Loop i++
        Else
            return FALSE

and there is no functional requirement to store or pre-compute all the permutations. Any non-functional requirement such as performance may be addressed with a non-functional solution such as memoization or caching.

Iteration

Mapping P to P' is an operation from one constant to another constant. This mapping can be represented as a function f. We can get any member of P as x' by f(x) where x is the corresponding member of P. This means that we can iterate over the entirety of P simply by constructing P. The good news is that this means we are no worse off spatially when we construct P' than we were with P. The bad news is that we are no better off.

The Bad News

Permutations are in NP and the only way to get back into P is to know something about:

  1. The nature of the Data
  2. The nature of the Question

Optimization based on the Data

If the data is not random or contains structural relationships then the search space can be pruned of values that cannot occur. For example, if in the tuple x it is always the case that when x1 = 0, 15 <= x2 <= 42 there is a constraint on the search space and we may not need to iterate all the permutations.

Optimization base on Question

If we are searching for the maximum of:

(x1) / (x2) + (x3)

Then we can prune x3 to a single value and similarly prune the pair (x1, x2).

The Good News

We never [outside of a classroom] need to produce the entirety of P all at once. There is always some reason we are producing it and looking at that reason allows us to optimize. The price for that optimization is a particular brittleness, but the naive solution of iterating all permutations is also brittle because once the problem hits a certain size it doesn't work.

Alternatives

Data Compression can push back the point at which the non-polynomial nature of combinations limits the size of the input set, but it can't eliminate it. TANSTAAFL. Data compression, like any optimization, only works when it reflects a structural characteristic of the problem.

Advice

  1. Tune the procedure for generating combinations for the problem domain.
  2. Tune the procedure for generating combination to those that are of interest to the specific question at hand.
  3. Tune the procedure for generating combinations to reflect structural properties of the data. Statistical analysis is a good place to start, try to avoid analysis that takes exponential time.

Knuth has written a whole book on strategies for solving combinatorial problems. He didn't find a general solution. He doesn't believe that he ever will, and he encourages readers to contact him if they do.

\$\endgroup\$
0
\$\begingroup\$

When I see "manipulate large data", I immediately think " bucket sort". I think this technique can work for your problem too. Say you have n lists and you store all permutations per list in a dedicated file. All you need to do to combine them together is store a current row index for each file, read it to memory and concatenate one after another and then, store the row to results file.

\$\endgroup\$
0
\$\begingroup\$

Holding all these lists in memory is going to be massive, hence running out of heap space. Printing them all out is going to be equally problematic as you can expect similar scaling problems and likely a bottleneck around your console if you're printing them straight out.

You can save some memory by storing your permutations in a tree structure, however this will still be pretty large. Also, be careful of repeated values in your list leading to repeated permutations (the lists of booleans in particular will result in a lot of repeated permutations if you treat each positional boolean as if it were unique).

\$\endgroup\$

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.