find combinatios of list items

Question

I'm having n inputLists with items. Now I want to calculate resultLists (of length n) containing all combinations of items in the original inputLists (taking one item of each inputList).

I think I should provide an example here (n=3):

inputList1: [item1, item2, item3]
inputList2: [item4]
inputList3: [item5, item6]

resultList1: [item1, item4, item5]
resultList2: [item1, item4, item6]
resultList3: [item2, item4, item5]
resultList4: [item2, item4, item6]
resultList5: [item3, item4, item5]
resultList6: [item3, item4, item6]

I'm feeling kind of stupid, but I have no idea how to implement (C++) a function creating these results for any n and any inputList lengths. I think I should use some sort of recursion, but I don't know how.
Any ideas?

[Here is a solution in Java](http://stackoverflow.com/a/10462803/312172), and here, more concise, and maybe similarly doable [in Scala](http://stackoverflow.com/a/5177163/312172). — user unknown, May 08 '12 at 16:26

jrok · Accepted Answer · 2012-05-08T16:00:13.380

A general idea, in pseudocode:

vector<item> List1, List2, List3;
// fill the lists

vector<item> v;
vector<vector<item>> results;

for each item i in List1
{
    v.push_back(i)
    for each item j in List2
    {
        v.push_back(j);
        for each item k in List3
        {
            v.push_back(k);
            results.push_back(v);
            v.pop_back();
        }
        v.pop_back();
    }
    v.pop_back();
}

To do this on variable number of lists, I'd go with recursive approach. Each for loop would then be replaced with a recursive function call. This function would need to accept a list of your inputLists, a results list, and a container that stores the intermediate result (v in the above example) as parameters.

Hope that helps.

This was easier than I thought. Thanks! – aLu May 09 '12 at 07:03 — aLu, May 09 '12 at 07:03

BatchyX · Answer 2 · 2012-05-08T16:18:12.977

Iterators are your friends here. two pseudocode versions without bothering about error checking or corner cases like zero-sized lists or the likes:

struct cartesian_product_iterator {
    int indexes[n] initialized to zeroes
    operator++() {
        a = 0
        indexes[a]++;
        while a < n and indexes[a] >= list[a].size()
            indexes[a] = 0
            a++;
    }
    operator *() {
        list<?> ret;
        for a in 0..n-1:
            ret.push_back(list[a][indexes[a]]);
        return ret;
    }
    past_the_end_iterator() { indexes[n-1] = list[n-1].size(); }
}

You might notice that the indexes array is just the decomposition of an integer into multiple bases. which leads to the second solution:

struct cartesian_product_iterator_2 {
    unsigned_or_arbitrarly_big_int a_large_number = 0;
    operator ++()  { a_large_number++; }
    operator *() {
        list<?> ret;
        unsigned_or_arbitrarly_big_int to_decompose = a_large_number;
        for a in 0..n-1:
            index = to_decompose % list[a].size();
            to_decompose /= list[a].size();
            ret.push_back(list[a][index]);
        }
        return ret;
    }
    past_the_end_iterator() {
       a_large_number = 1;
       for each l in list:
           a_large_number *= l.size();
    }
}

As for which one is best/faster, i don't really have an idea.

find combinatios of list items

2 Answers2