CODEWITHSUNDEEP
c++cartesian-product
aLu
aLu

Reputation: 47

find combinatios of list items

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?

Upvotes: 1

Views: 140

Answers (2)

BatchyX
BatchyX

Reputation: 5114

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.

Upvotes: 0

jrok
jrok

Reputation: 55395

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.

Upvotes: 1

Related Questions