# Algorithm of combinations (problem with time and space)

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>>();
int n = combinazioni.size();
ArrayList<Elemento> temp = new ArrayList<Elemento>();
// 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>();
}
// 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;
}
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;
}
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;
• I just want a hand to understand where the algorithm takes time or a better solution , different from mine – Pino Jul 6 '15 at 10:58
• What do you do with the results after you have generated them? Your combine method seems.... useless. – Simon Forsberg Jul 6 '15 at 11:02
• With how many elements do you call this method? – user140547 Jul 6 '15 at 11:06
• @Pino What kind of "rules" is it that you are trying to match? Explaining the problem behind the code will helps us give you a better solution. It is quite likely that you can complete this in an entirely different way. – Simon Forsberg Jul 6 '15 at 12:24

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.

• Hello , I do this when I call GestoreRegole.esegui . In practice, for each combination generated do I rate rules . – Pino Jul 11 '15 at 11:43
• @Pino The problem is that you generate first. You should not generate the combinations and store them in a list. You should do the work that you are doing without storing all the combinations. – Simon Forsberg Jul 11 '15 at 11:44

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.

• hello how the cartesiaproduct ? I propose how to write code in Java ? – Pino Jul 6 '15 at 11:37
• I have to downvote because I don't believe this solves the underlying problem. Storing all the possible combinations is the problem. Iterating is the answer (or my answer at least) – Simon Forsberg Jul 11 '15 at 11:38
• @SimonAndréForsberg Who says that the cartesian product stores all the elements? It does not! +++ Still, it's a collection and therefore limited to int-valued size, but memory is not a problem here. – maaartinus Jul 11 '15 at 12:54
• Sorry, it was unclear from the wording in your answer that the cartesian product was lazy. However, using the cartesian product does not help here as far as I can see. You can't have it return sets/lists of different size. Remember that the results should be [A], [B], [C], [A B], [A C], [B C], [A B C]. That's not cartesian. – Simon Forsberg Jul 11 '15 at 13:05
• @SimonAndréForsberg It's actually flattened $\{\{A\}, \emptyset\} \times \{\{B\}, \emptyset\} \times \{\{C\}, \emptyset\}$, but you're right, some more processing may be needed, e.g., dropping the empty set. No idea, if the OP needs a List or a Set (for sure, they don't need a LinkedList). And most probably, the processing will take too long anyway and the OP should do something else instead (XY problem). – maaartinus Jul 11 '15 at 13:39

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.

• I tried to increase the memory consumed and java netbeans but with few results . I need to generate all possible combinations of chemical compounds from some elements ( H , O, C , N ) – Pino Jul 6 '15 at 11:33
• Increasing the memory available will postpone the problem, not solve it. Changing between arrays and lists is a quite minimal difference, this problem needs to be solved in a different way. – Simon Forsberg Jul 6 '15 at 12:25
• Simon Andrè Forsberg, and how can I fix it ? – Pino Jul 6 '15 at 12:30
• @SimonAndréForsberg, I actually mentioned in the last paragraph that he should try to avoid enumerating all combinations. But if the problem is to enumerate all combinations in some data structure, these are some possibilities to increase the number of possible combinations . – user140547 Jul 6 '15 at 12:34