: On 19 May 2012 01: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:
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. -- http://mail.python.org/mailman/listinfo/python-list