61 lines
2.1 KiB
Python
61 lines
2.1 KiB
Python
from operator import itemgetter
|
|
|
|
DEBUG = False # like the built-in __debug__
|
|
|
|
def spermutations(n):
|
|
"""permutations by swapping. Yields: perm, sign"""
|
|
sign = 1
|
|
p = [[i, 0 if i == 0 else -1] # [num, direction]
|
|
for i in range(n)]
|
|
|
|
if DEBUG: print ' #', p
|
|
yield tuple(pp[0] for pp in p), sign
|
|
|
|
while any(pp[1] for pp in p): # moving
|
|
i1, (n1, d1) = max(((i, pp) for i, pp in enumerate(p) if pp[1]),
|
|
key=itemgetter(1))
|
|
sign *= -1
|
|
if d1 == -1:
|
|
# Swap down
|
|
i2 = i1 - 1
|
|
p[i1], p[i2] = p[i2], p[i1]
|
|
# If this causes the chosen element to reach the First or last
|
|
# position within the permutation, or if the next element in the
|
|
# same direction is larger than the chosen element:
|
|
if i2 == 0 or p[i2 - 1][0] > n1:
|
|
# The direction of the chosen element is set to zero
|
|
p[i2][1] = 0
|
|
elif d1 == 1:
|
|
# Swap up
|
|
i2 = i1 + 1
|
|
p[i1], p[i2] = p[i2], p[i1]
|
|
# If this causes the chosen element to reach the first or Last
|
|
# position within the permutation, or if the next element in the
|
|
# same direction is larger than the chosen element:
|
|
if i2 == n - 1 or p[i2 + 1][0] > n1:
|
|
# The direction of the chosen element is set to zero
|
|
p[i2][1] = 0
|
|
if DEBUG: print ' #', p
|
|
yield tuple(pp[0] for pp in p), sign
|
|
|
|
for i3, pp in enumerate(p):
|
|
n3, d3 = pp
|
|
if n3 > n1:
|
|
pp[1] = 1 if i3 < i2 else -1
|
|
if DEBUG: print ' # Set Moving'
|
|
|
|
|
|
if __name__ == '__main__':
|
|
from itertools import permutations
|
|
|
|
for n in (3, 4):
|
|
print '\nPermutations and sign of %i items' % n
|
|
sp = set()
|
|
for i in spermutations(n):
|
|
sp.add(i[0])
|
|
print('Perm: %r Sign: %2i' % i)
|
|
#if DEBUG: raw_input('?')
|
|
# Test
|
|
p = set(permutations(range(n)))
|
|
assert sp == p, 'Two methods of generating permutations do not agree'
|