How to generate only rotationally-unique permutations?

[John O'Hagan]

On Sat, 19 May 2012 09:15:39 +0100
Arnaud Delobelle <arnodel at gmail.com> wrote:

> On 19 May 2012 06: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:
> 
> This makes me think of Lyndon words.  A Lyndon word is a word which is
> the only lexicographical minimum of all its rotations.  There is a
> very effective way of generating Lyndon words of length <= n.  It may
> be possible to adapt it to what you want (obviously as Lyndon words
> are aperiodic you'd have to generate Lyndon word of length d | n when
> suitable).
> 

Thanks for your suggestion. The Lyndon word generators I found were not
quite what I was after as they didn't guarantee giving sequences with the same
elements. but your suggestion led me to necklaces:

http://en.wikipedia.org/wiki/Necklace_ (combinatorics)
 
of which Lyndon words represent a special aperiodic case. I found these
algorithms for generating necklaces:

http://www.sagenb.org/src/combinat/necklace.py

which seems to be exactly what I want. Thanks!

Regards,
--
John