6
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – pascal Mar 18 '12 at 3:34
  • $\begingroup$ By rotation I assume you mean permutation? $\endgroup$ – Deathbreath Mar 19 '12 at 15:18
  • $\begingroup$ 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) $\endgroup$ – pascal Mar 19 '12 at 20:35
  • $\begingroup$ For a potential tuple, output only those which are lexicographically least among all their possible rotations. $\endgroup$ – hardmath Mar 8 '16 at 18:18
2
$\begingroup$

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
|cite|improve this answer
$\endgroup$

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.