How to generate only rotationally-unique permutations?

[Zero Piraeus]

:

On 19 May 2012 01:23, John O'Hagan <research at johnohagan.com> wrote:
> How to generate only the distinct permutations of a sequence which are not
> rotationally equivalent to any others? More precisely, to generate only the most
> "left-packed" of each group of rotationally equivalent permutations, such that
> for each permutation p:

It's late and I'm tired (and the solution below isn't a generator), but ...

itertools.permutations() generates results in lexicographic order [1],
so if you reverse-sort the sequence before processing it, when you get
a sequence back whose first item isn't the maximum, you'll know that
you've got all the sequences whose first item *is* the maximum - which
means you can bail at that point.

Wow, that's a nasty sentence. As I said, tired. Anyway - you'll get
dupes if there are non-unique items in the rest of the sequence, so
some form of filtering is required, but you could use a set to handle
that. Something like:

    from itertools import permutations

    def rot_uniq_perms(seq):
        result = set()
        seq = sorted(seq, reverse=True)
        maximum = seq[0]
        for x in permutations(seq):
            if x[0] != maximum:
                break
            else:
                result.add(x[::-1])
        return result

No idea how this performs compared to your existing solution, but it
might be a starting point.

[1] http://docs.python.org/library/itertools.html#itertools.permutations

 -[]z.