How to make Combinatorics on the fly

Question

I have a very strange problem that has some limitations that make it difficult to solve. I have a list of lists, and I want to make combinations of all the elements in these lists. Each element has a name and a value. Here is an example:

Main list:

• List 01:
  • Item 01: name: name01, value: value01
  • Item 02: name: name02, value: value02
• List 02:
  • Item 01: name: name03, value: value03
• List 03:
  • Item 01: name: name04, value: value04
  • Item 02: name: name05, value: value05

The end result should look like this:

Some listings:

• Item 01: name01: value01, name03: value03, name04: value04
• Item 02: name02: value02, name03: value03, name04: value04
• Item 03: name03: value03, name03: value03, name04: value04
• Item 04: name01: value01, name03: value03, name04: value05
• Item 05: name02: value02, name03: value03, name04: value05
• Item 06: name03: value03, name03: value03, name04: value05

The new list contains items that act as a hash map.

The limitations are as follows:

• I cannot compile new lists and mix them, because these lists can grow quite large quite quickly.
• I use some kind of observer-like api, so I need to inform the observer of the result as soon as possible so that I do not use a lot of memory.

In other words, the combination generator can be equipped with X number of lists, each of which can contain N number of elements, and I have to generate their combinations without using too much memory.

I do not expect to work with more than 5 lists at a time, but I would like to make the algorithm as stable as possible for changing the code.

I am solving a problem in java, but the algorithm should work the same in other languages, because it is likely to be translated.

Do you have any ideas, suggestions?

Thanks in advance.

PS I do not think recursion will work well. I play with the idea of ​​using a while loop and some nested loops, but it becomes very difficult to imagine how this should work.

Answer 1

So, this is a Cartesian product, you after?

Assume 3 lists with elements 2, 1 and 3. You would end 2 * 1 * 3 combinations = 6. (abstract: a * b * ... * i)

Now you take 6 numbers from 0 to 5.

void getCombiFor (int i, List <List <Integer>> li) { if (li.length > 0) { int idx = i % li.get (0).size (); System.out.print (li.get (0).get(idx)); getCombiFor (i - idx, li.remove (0)); } System.out.println (); } // pseudocodeline: List li = List (List ('a', 'b'), List ('c'), List ('d', 'e', 'f')) for (int i = 0; i < 6; ++i) { getCombiFor (i, li); } 

Example:

 Lists = ((a,b), (c), (d,e,f)) acd bcd acf bcf ace bce 

Answer 2

You do not need to use memory to solve this problem. You can get the Nth element of list math without creating whole combinations. It is explained here

Answer 3

How about creating an array of indexes, one for each of the lists? The current combination could be read by running get () on each list in turn. Each index will be zero - then move on to the next combination that you really act

 index[0]++; if (index[0] >= list[0].size()) { index[0] = 0; index[1]++; if (index[1] >= list[1].size()) { ... } } 

(Inclusion of the nested if left in the iteration as an exercise for the reader.)

Answer 4

Why don't you make a hash map?

 Map<String,Map<String,String>> mainMap = new HashMap<String,Map<String,String>>(); for(List l : lists) { for(Data d : l) { String item = d.item; String name = d.name; String value = d.value; Map<String,String> itemMap = mainMap.get(item); if(item == null) { itemMap = new HashMap<String,String>(); mainMap.put(item,itemMap); } itemMap.put(name,value); } } 

later, you want to get all the values ​​for a given name, regardless of which element?

 List<String> getValuesForName(String name) { List<String> list = new LinkedList<String>(); for(Map<String,String map : mainMap) { String value = map.get(name); if(value != null) list.add(value); } return list; }