Iterating over the cartesian product of a list of lists

Question

The problem is a generalization of the folling simple problem:

Given 3 lists of elements, I can loop over the pairings between all 3 lists by folling pseudocode:

foreach( element1 in list1 )
    foreach( element2 in list2 )
        foreach( element3 in list3 )
            dosomething( element1, element2, element3 )

So it will pair an element out of each list with every combination of elements out of the other lists.

Now I have a list of lists of elements, so there are N lists. How can I do the same principle?

My best shot at it so far is to calculate an index for each pairing and iterate over the indices calculated this way:

Let's say the pairing with the first element of every list gets index 0. To illustrate, let's call this {0,0,0,...}. The next index (1) would be {1,0,0,...}. If the first list has size0 elements, the pairing {0,1,0,...} would get index size0. The pairing {2,4,1,0,...} would get index (1*size1 + 4*size0 + 2).

Is there a better way of doing this? Are there languages with this feature built in? Currently I need it in C++, but a general solution is an answer to this question. Language specific implementations can be left in the comments.

Answer 1

using recursion

#include <iostream>
#include <vector>

template <typename T>
void cartesian_product_helper(const std::vector<std::vector<T>>& lists, std::vector<T>& current_product, size_t depth) {
    if (depth == lists.size()) {
        for (const T& element : current_product) {
            std::cout << element << " ";
        }
        std::cout << std::endl;
    } else {
        for (const T& element : lists[depth]) {
            current_product.push_back(element);
            cartesian_product_helper(lists, current_product, depth + 1);
            current_product.pop_back();
        }
    }
}

template <typename T>
void cartesian_product(const std::vector<std::vector<T>>& lists) {
    std::vector<T> current_product;
    cartesian_product_helper(lists, current_product, 0);
}

int main() {
    std::vector<std::vector<int>> lists = {{1, 2}, {3, 4}, {5, 6}};
    cartesian_product(lists);
    return 0;
}

Answer 2

You can do it just like counting in decimal, except that the base of each digit is the length of the corresponding list:

vector<size_t>: sizes, indexes;
vector<T>: elements;

foreach (auto list: lists) {
    sizes.push_back(list.size());
    indexes.push_back(0);
    elements.push_back(list[0]);
}

int digit = 0;
do {
    doSomething(elements);

    for (digit = (int)indexes.size()-1; digit>=0; --digit) {
        if (++(indexes[digit]) >= sizes[digit]) {
            // carry
            indexes[digit] = 0;
            elements[digit] = lists[digit][0];
        } else {
            elements[digit] = lists[digit][indexes[digit]];
            break;
        }
    }
} while(digit>=0);