How to generate only rotationally-unique permutations?

[John O'Hagan]

On Sat, 19 May 2012 04:21:35 -0400
Zero Piraeus <schesis at gmail.com> wrote:

> :
> 
> 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.

Thanks for your reply, but I can't profitably use itertools.permutations, as my
sequences have repeated elements, so I was using a python implementation of the
next_permutation algorithm, which yields only distinct permutations. Your
trick of bailing when x[0] != maximum is, I think, another version of what my
attempt did, that is, remove the maximum, permute the rest, then replace it.
But the problem remains of what to do if there are several maxima.

That is obviated by a solution suggested by another reply, of using a
necklace generator.

Thanks again,
--
John