Algorithm of combinations (problem with time and space)

Question

My algorithm generates combinations of elements. For example, having [A, B, C ] creates the following combinations [ A ], [ B ], [ C ], [ AB ], [ AC ], [ B, C ], [ ABC ].

Unfortunately for items too large too long and too much memory space, I get java.lang.OutOfMemory thrown. How can I fix?

public void combine() {
    this.findAllCombinations(combinazioneMassima);
}

private static class Node{
    int lastIndex = 0;
List<Elemento> currentList;
public Node(int lastIndex, List<Elemento> list) {
        this.lastIndex = lastIndex;
        this.currentList = list;
}
public Node(Node n) {
        this.lastIndex = n.lastIndex;
        this.currentList = new ArrayList<Elemento>(n.currentList);
}
}

public List<List<Elemento> > findAllCombinations(List<Elemento> combinazioni) {
    Date dataInizio = new Date();
    List<List<Elemento>> resultList = new ArrayList<List<Elemento>>();
    LinkedList<Node> queue = new LinkedList<Node>();
    int n = combinazioni.size();
    ArrayList<Elemento> temp = new ArrayList<Elemento>();
    temp.add(combinazioni.get(0));
    queue.add(new Node(0, temp));
    // add all different integers to the queue once.
    for(int i=1;i<n;++i) {
            if(combinazioni.get(i-1) == combinazioni.get(i)) continue;
            temp = new ArrayList<Elemento>();
            temp.add(combinazioni.get(i));
            queue.add(new Node(i, temp));
    }
    // do bfs until we have no elements
    while(!queue.isEmpty()) {
            Node node = queue.remove();
            if(node.lastIndex+1 < n) {
                    Node newNode = new Node(node);
                    newNode.lastIndex = node.lastIndex+1;
                    newNode.currentList.add(combinazioni.get(node.lastIndex+1));
                    queue.add(newNode);
            }
            for(int i=node.lastIndex+2;i<n;++i) {
                    if(combinazioni.get(i-1) == combinazioni.get(i)) continue;
                    // create a copy and add extra integer
                    Node newNode = new Node(node);
                    newNode.lastIndex = i;
                    newNode.currentList.add(combinazioni.get(i));
                    queue.add(newNode);
            }
            GestoreRegole gestoreRegole = new GestoreRegole();
            gestoreRegole.esegui(node.currentList);
    }
    Date dataF = new Date();
    long tempo = dataF.getTime() - dataInizio.getTime(); 
    logger.info ("durata genera combinazioni: " + tempo);
    return resultList;

Answer 1

The Italian identifiers is making your code harder to understand, first of all.

There is only one way to solve your problem. Don't store all of the combinations at once.

Use an Iterator instead. Iterate through the combinations one by one, and do the work that you need to do for each one. Without adding the combinations to a List. Then throw the combination away and move on to the next one. There are many ways that you can retrieve a specific combination without storing all combinations at once. That's something that you can iterate over.

When computing combinations it can often lead to a huge amount of possible combinations, which is why you need to simplify the problem as much as possible. Consider if there is any way you can group the combinations so that you can analyze many of them at once. I used several tricks like this that helped me greatly in Analyzing Minesweeper Probabilities. I don't know enough of your use case to know whether or not you can simplify it, but I believe that you somehow can.

Answer 2

What you're doing is generating all subsets.

He gives me java.lang.OutOfMemory when the list contains 256 items or more than 256

Did you try to compute how big your set gets? It's \$2^{256}\$, i.e., about \$10^{77}\$, i.e.,

115792089237316195423570985008687907853269984665640564039457584007913129639936

Go buy some more memory, but note that there are just \$10^{80}\$ atoms in your universe.

---

If you switched to some saner list sizes, like 40, you'll still get an OOM error as the set would be too big. But you could generate and process it lazily: Processing \$2^{40}\$ elements takes a while but is feasible.

For this you could use Guava's Lists#cartesianProduct.

Review

I didn't write a real review as the code is not your (main) problem. But I'll do it if anyone requests.

Answer 3

I think the problem is that you use just too much memory when enumerating that many elements. You can try to increase the memory available to Java by using -Xmx or using array instead of Lists which may use less memory. But if you try to put that many elements in a list, you need much memory.

Since a power set has 2^n elements, doubling the memory will only make it possible to add one more element to the list, so it has only limited effect.

Why do you need such a list? For an algorithm you might try not use a brute-force algorithm which needs to enumerate all combinations.