snippetMinor
How to enumerate a product set?
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?
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.
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.