How to do Combinatorics on the Fly

Question

I have a very weird problem which has some constrains that make it difficult to solve. I have a list of lists and I want to do the combinations of all items in those lists. Each item 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 List:

• 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 pretty much contains items that act like hash map.

The constrains are the following:

1. I cannot collect into new lists and mix them because these lists could quickly grow quite big.
2. I am using some kind of observer-like api so I need to let the observer about the result as soon as possible so that I don't use to much memory.

In other words this combinations generator may be feeded with X number of lists each one of which could contain N number of items and I must generate the combinations of them without using too much memory.

I don't expect to work with more then 5 list at a time but I would like to make the algorithm as resilient to code changes as possible.

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

Do you have any ideas, suggestions?

Thanks in advance.

P.S. I don't think that a recursion will work well. I am toying with the idea of using a while loop and some nested loops but it is getting really difficult to envision how this should work.

Answer 1

So this is the cartesian product, you're after?

Assume 3 lists, with 2, 1 and 3 Elements. You would end in 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

How about creating an array of indices, one for each of the given lists? The current combination could be read off by doing get() on each list in turn. Each index would at zero -- then to advance to the next combination you do in effect

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

(Turning the nested if's into an iteration left as an exercise for the reader.)

Answer 3

Why don't you actually make a hashmap?

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, no matter what item?

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;
}

Answer 4

You don't need to use any memory to solve this problem. It's possible to get the Nth element of list mathematicaly, without creating the whole combinations. It is explained here