# Algorithm for generating all cartesian products, without rotations

(Not sure if that's the right SX site? I don't need actual code, so…)

I'm looking for an algorithm that generates all cartesian products for a list of sets, but skips tuples that are just rotations of previously issued tuples in a smart way.

Here, $(a_0,\dotsc,a_n)$ is a rotation of $(b_0,\dotsc,b_n)$ iff $\exists x : \forall i \in [0,\dotsc,n]: a_i = b_j \text{ with } j = i + x \mod n$.

For example, for $f(\{1, 2\}, \{1, 2, 3\})$ the output should be $\{(1,1), (1,2), (1,3), (2,2), (2,3)\}$, i.e. without $(2,1)$ because it's a rotation of $(1,2)$.

• It's easy to convert each tuple from/to an integer, so when about to generate a tuple, one could look if any of its rotations map to a smaller integer than the current tuple and discard it. But I'm hoping there's an algorithm that's faster than one that generates all products. – pascal Mar 18 '12 at 3:34
• By rotation I assume you mean permutation? – Deathbreath Mar 19 '12 at 15:18
• No, the tuple is supposed to be a ring, i.e. $a_0$ is the successor of $a_n$, $a_1$ that of $a_0$, etc. The order stays fixed, but which element in the ring gets index 0 may change. (edited the question with a proper expression for what I mean by "rotation". That I'm speaking about tuples isn't helping I guess, I mean circularly linked lists: don't care about the start, just the order) – pascal Mar 19 '12 at 20:35
• For a potential tuple, output only those which are lexicographically least among all their possible rotations. – hardmath Mar 8 '16 at 18:18

This is the brute-force way (in Python), maybe it's interesting to somebody:

def rotate_product(*xs):
# map integer to tuple
def from_int(i):
tup = []
for x in xs:
tup.append(x[i % len(x)])
i /= len(x)
return tuple(tup)

# map tuple to integer, or -1 if impossible.
def to_int(tup):
i = 0
mul = 1
for t, x in zip(tup, xs):
if t not in x:
return -1
i += mul * x.index(t)
mul *= len(x)
return i

# map integer to tuple, if no rotation of smaller tuple
def make_tuple(i):
tup = from_int(i)
for k in range(1, len(xs)):
if 0 <= to_int(tup[k:] + tup[:k]) < i:
return None
return tup

# total number of possible tuples
n = 1
for x in xs:
n *= len(x)

# brute force through all possibilities
for i in range(n):
t = make_tuple(i)
if t:
yield t