On Sat, 19 May 2012 09:15:39 +0100 Arnaud Delobelle <arno...@gmail.com> wrote:
> On 19 May 2012 06:23, John O'Hagan <resea...@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 -- http://mail.python.org/mailman/listinfo/python-list