Algorithm for generating all cartesian products, without rotations

Question

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

Answer 1

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