5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Antun Tun Apr 8 '14 at 19:05
  • 1
    $\begingroup$ see stackoverflow.com/a/533917/3456281 $\endgroup$ – Jasper Apr 8 '14 at 19:56
  • 2
    $\begingroup$ This is basically a programming question, which is off-topic, here. $\endgroup$ – David Richerby Apr 8 '14 at 22:28
  • $\begingroup$ Your question seems a bit simmilar to my question here. cs.stackexchange.com/questions/11046/… $\endgroup$ – Nejc Apr 9 '14 at 9:47
  • $\begingroup$ @DavidRicherby Knuth wrote a whole volume of TAoCP on questions such as this, so ymmv. $\endgroup$ – Raphael Apr 9 '14 at 14:54
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ (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?) $\endgroup$ – Steven Stadnicki Apr 10 '14 at 22:11
2
$\begingroup$

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 ) {
        result.add(x ++ list)
      }
    }

    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.

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – Yuval Filmus Apr 9 '14 at 13:50
  • $\begingroup$ I guess it's because some pairs are never seen, any hints to prove this? $\endgroup$ – saadtaame Apr 9 '14 at 14:08
  • $\begingroup$ Try it out and see. $\endgroup$ – Yuval Filmus Apr 11 '14 at 4:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.