How can I compute a Cartesian product iteratively?

Question

This question asks how to compute the Cartesian product of a given number of vectors. Since the number of vectors is known in advance and rather small, the solution is easily obtained with nested for loops.

Now suppose that you are given, in your language of choice, a vector of vectors (or list of lists, or set of sets, etc.):

l = [ [1,2,3], [4,5], [6,7], [8,9,10], [11,12], [13] ]

If I was asked to compute its Cartesian product, that is

[ [1,4,6,8,11,13], [1,4,6,8,12,13], [1,4,6,9,11,13], [1,4,6,9,12,13], ... ]

I would proceed with recursion. For example, in quick&dirty python,

def cartesianProduct(aListOfLists):
    if not aListOfLists:
        yield []
    else:
        for item in aListOfLists[0]:
            for product in cartesianProduct(aListOfLists[1:]):
                yield [item] + product

Is there an easy way to compute it iteratively?

(Note: The answer doesn't need to be in python, and anyway I'm aware that in python itertools does the job better, as in this question.)

Answer 1

1) Create a list of indexes into the respective lists, initialized to 0, i.e:

indexes = [0,0,0,0,0,0]

2) Yield the appropriate element from each list (in this case the first).

3) Increase the last index by one.

4) If the last index equals the length of the last list, reset it to zero and carry one. Repeat this until there is no carry.

5) Go back to step 2 until the indexes wrap back to [0,0,0,0,0,0]

It's similar to how counting works, except the base for each digit can be different.

---

Here's an implementation of the above algorithm in Python:

def cartesian_product(aListOfList):
    indexes = [0] * len(aListOfList)
    while True:
        yield [l[i] for l,i in zip(aListOfList, indexes)]
        j = len(indexes) - 1
        while True:
            indexes[j] += 1
            if indexes[j] < len(aListOfList[j]): break
            indexes[j] = 0
            j -= 1
            if j < 0: return

---

Here is another way to implement it using modulo tricks:

def cartesian_product(aListOfList):
    i = 0
    while True:
        result = []
        j = i
        for l in aListOfList:
             result.append(l[j % len(l)])
             j /= len(l)
        if j > 0: return
        yield result
        i += 1

Note that this outputs the results in a slightly different order than in your example. This can be fixed by iterating over the lists in reverse order.

Answer 2

Since you asked for a language-agnostic solution, here is one in bash, but can we call it iterative, recursive, what is it? It's just notation:

echo {1,2,3},{4,5},{6,7},{8,9,10},{11,12},13

maybe interesting enough.

1,4,6,8,11,13 1,4,6,8,12,13 1,4,6,9,11,13 1,4,6,9,12,13 1,4,6,10,11,13 ...