To revisit a question which I'm sure none of you remember from when I posted it
a year or so ago - there were no takers at the time - I'd like to try again with
a more concise statement of the problem:
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:
p == min(p[i:] + p[:i] for i in range(len(p)) if p[i - 1] == max(p))
At the moment I'm generating all the distinct permutations and filtering the
ones which fail this test, but the inefficiency bothers me and slows down the
program I'm feeding the results to..
Below is some code which removes the maxima from a sequence, permutes it using
some permuting function, and tries to reinsert the maxima in such a way as to
comply with the above requirement:
from itertools import combinations_with_replacement as cwr
def rot_uniq_perms(seq, permfunc):
ma = max(seq)
maxnum = seq.count(ma) - 1
nonmax = [i for i in seq if i != ma]
if nonmax:
for perm in permfunc(nonmax):
perm = perm + [ma]
if maxnum:
inserts = [i for i in range(1, len(perm))
if perm[i] >= perm[0]]
insert_combs = cwr(inserts, maxnum)
for points in insert_combs:
result = perm[:]
for point in reversed(points):
result.insert(point, ma)
if result[:point + 1] > result[point + 1:]:
break
else:
yield result
else:
yield perm
else:
yield seq
This is the most success I've had so far, but unfortunately still generates
2-3% false positives.
I'm also trying a similar approach using the minima instead, which is
intended to generates only the minimum of each rotationally equivalent
group such that:
p == min(p[i:] + p[:i] for i in range(len(p)))
but so far, despite seeming simpler, I've had difficulty getting my head around
it, and it performs far worse than the above code.
I'm looking for any method which would guarantee rotational uniqueness. I
also get the feeling I'm barking up the wrong tree. Any suggestion?
Thanks,
--
John
--
http://mail.python.org/mailman/listinfo/python-list
