# How to enumerate a product set?

I am coding a procedure that takes an integer $d$, and generates $d$ finite lists $X_1 \ldots, X_d$ of elements. I would then like for it to output a list of the elements in the product set $X_1 \times \cdots \times X_d$.

I can't use nested for-loops because $d$ can vary so I wouldn't know how many to nest. I'm sure there's a totally standard solution to this problem, but I don't know enough to search for it successfully either here on online.

For what it's worth, here's one dumb solution I came up with. Let $b$ be the maximum cardinality of the sets $X_i$. Then run a single loop for $n$ running from $0$ to $b^d$; for each $n$, write it in base $b$ and use the $i^{\rm th}$ digit to read off the element of $X_i$ corresponding to that digit (and ignore if any of those digits are too big for the cardinality of the corresponding set). This will work, but feels like a pretty stupid solution.

What's the standard way of doing this?

• I don't know Python but here is my suggestion from C#, if that helps anything to you. ---------- You can do this through sth called "jagged arrays" but better solution is through LINQ, it is part of .NET for several years now. You need a "Cartesian product" of returned data. Here is a similar question: stackoverflow.com/questions/4423838/… Hope I helped a bit. – Antun Tun Apr 8 '14 at 19:05
• – Jasper Apr 8 '14 at 19:56
• This is basically a programming question, which is off-topic, here. – David Richerby Apr 8 '14 at 22:28
• Your question seems a bit simmilar to my question here. cs.stackexchange.com/questions/11046/… – Nejc Apr 9 '14 at 9:47
• @DavidRicherby Knuth wrote a whole volume of TAoCP on questions such as this, so ymmv. – Raphael Apr 9 '14 at 14:54

There is a legitimate mathematical question here: find an encoding or $X_1\times X_2\times\cdots\times X_d$. The idea is to use mixed base. As you note, if all sets have cardinality $b$, then you can use base $d$ encoding. If the sets have different cardinalities, then you use a mixed base approach. Suppose $|X_i| = b_i$. The choice of elements $c_i \in X_i$ (say $0 \leq c_i < b_i$) can be encoded as follows: $$c_1 + b_1 c_2 + b_1 b_2 c_3 + \cdots + b_1 b_2 \cdots b_{d-1} c_d.$$ Every number in the range $0$ to $b_1 b_2 \cdots b_d - 1$ encodes a unique choice of element from $X_1\times X_2\times\cdots\times X_d$.

There is also a programming question here: how to generate the list. The idea is to use a generalization of a binary counter, familiar for students of amortized complexity. There is an array $c$ of length $d$, where $c_i$ is going to encode a choice of element in $X_i$. At each step, we update this "counter" by increasing it by 1. We start by increasing $c_1$ by 1. If $c_1 < b_1$, everything is fine. Otherwise, there is carry: we set $c_1 = 0$, and increase $c_2$ by 1. And so on. The resulting sequence is a lexicographically ordered list of elements in $X_1\times X_2\times\cdots\times X_d$. The amortized complexity per step (assuming $b_i > 1$ for all $i$) is $O(1)$.

Notice the similarity between the encoding in the first half and the algorithm in the second half.

• (Note that it's not trivial that the amortized complexity is constant, especially since a single update can involve $O(d)$ steps - I encourage OP to think about the binary case to try and figure this out. (Hint: how many times does each bit flip as you go from $0$ to $2^d-1$? How many total bit flips does this produce?) – Steven Stadnicki Apr 10 '14 at 22:11

You stated that you can do nested loops like

for x1 in X1 {
...
for xd in Xd {
output [x1, ..., xd]
}
}


if dimension $d$ is known. This exact thing does not work with arbitrary $d$, of course, but you can do essentially the same thing using recursion; you just nest by calling recursively. This works because all for loops have the same form.

cartesian(X) = cartesianHelper(X,0)

cartesianHelper(X,i) {
if ( X.size <= i ) {
return []
}
else {
result = []

rest = cartesianHelper(X, i+1)
foreach ( x in X[i] ) {
foreach ( list in rest ) {
}
}

return result
}
}


I assume that the sets $X_i$ are given in an array or a similar data structure.

Note that such things are much neater to express in function languages.

Recursion/Iteration

The Cartesian product of $d$ sets can be defined inductively by first taking the product of the last $d-1$ sets: $X_2,\dots,X_d$ and then taking the product of the result and the first set $X_1$. So all you need is a procedure to multiply tow sets.

A different method

This method works only if the cardinalities are pairwise relatively prime (as Yuval pointed out). Let $n = card(X_1)\times\dots\times card(X_d)$. Allocate a $n\times d$ array to host the elements of the tuples and do the following for every row $i$: copy the elements of $X_i$ and put them on row $i$ of the array. Keep doing this until the row is full. You'll end up generating all tuples in the product set.

Example Say we want to compute $\{1,2\}\times \{1,2,3\}\times\{1\}$. We allocate a $6\times 3$ array.

. . .
. . .
. . .
. . .
. . .
. . .


copy the elements of $\{1,2\}$ on the first row until it's full.

1 . .
2 . .
1 . .
2 . .
1 . .
2 . .


Do the same to the other rows. The result is:

1 1 1
2 2 1
1 3 1
2 1 1
1 2 1
2 3 1


This takes $\cal O(nd)$.

• The new method works only if the cardinalities are pairwise relatively prime. Try for example $X_1 = \{1,2\}$ and $X_2 = \{1,2,3,4\}$. You'll only get $(1,1),(2,2),(1,3),(2,4)$. – Yuval Filmus Apr 9 '14 at 13:50
• I guess it's because some pairs are never seen, any hints to prove this? – mrk Apr 9 '14 at 14:08
• Try it out and see. – Yuval Filmus Apr 11 '14 at 4:41