HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to enumerate a product set?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
productsetenumeratehow

Problem

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?

Solution

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 1$ for all $i$) is $O(1)$.

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

Context

StackExchange Computer Science Q#23556, answer score: 3

Revisions (0)

No revisions yet.