Permutations by swapping
Generate permutations of n items using algorithms based on swapping. Also generate the sign of the permutation which is +1 when the permutation is generated from an even number of swaps from the initial state, and -1 for odd.
Permutations by swapping is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Such data are of use in generating the determinant of a square matrix and any functions created should bear this in mind.
- References
Python
When saved in a file called spermutations.py it is used in the Python example to the Matrix arithmetic task.
<lang python>
Implementation of: http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm#Even.27s_speedup
Also see: http://www.cut-the-knot.org/Curriculum/Combinatorics/JohnsonTrotter.shtml
debug = False
def spermutations(n):
'permutations by swapping. Yields: perm, sign'
sign = 1
lowest = [-1, 0, -1] # [num, direction, index]
p = [[i, 0 if i==0 else -1, i] # [num, direction, index]
for i in range(n)]
if debug: print ' #', p
yield tuple(pp[0] for pp in p), sign
while True:
if all(pp[1] == 0 for pp in p):
# Not moving
break
largest = max(p, key=lambda pp: pp if pp[1] else lowest)
sign *= -1
n1, d1, i1 = largest
if d1 == -1:
# Swap down
n2, d2, i2 = p[i1-1]
p[i1] = [n2, d2, i1]
p[i2] = [n1, d1, i2]
# 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
n2, d2, i2 = p[i1+1]
p[i1] = [n2, d2, i1]
p[i2] = [n1, d1, i2]
# 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 pp in p:
n3, d3, i3 = 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'</lang>
- Sample output
Permutations and sign of 3 items Perm: (0, 1, 2) Sign: 1 Perm: (0, 2, 1) Sign: -1 Perm: (2, 0, 1) Sign: 1 Perm: (2, 1, 0) Sign: -1 Perm: (1, 2, 0) Sign: 1 Perm: (1, 0, 2) Sign: -1 Permutations and sign of 4 items Perm: (0, 1, 2, 3) Sign: 1 Perm: (0, 1, 3, 2) Sign: -1 Perm: (0, 3, 1, 2) Sign: 1 Perm: (3, 0, 1, 2) Sign: -1 Perm: (3, 0, 2, 1) Sign: 1 Perm: (0, 3, 2, 1) Sign: -1 Perm: (0, 2, 3, 1) Sign: 1 Perm: (0, 2, 1, 3) Sign: -1 Perm: (2, 0, 1, 3) Sign: 1 Perm: (2, 0, 3, 1) Sign: -1 Perm: (2, 3, 0, 1) Sign: 1 Perm: (3, 2, 0, 1) Sign: -1 Perm: (3, 2, 1, 0) Sign: 1 Perm: (2, 3, 1, 0) Sign: -1 Perm: (2, 1, 3, 0) Sign: 1 Perm: (2, 1, 0, 3) Sign: -1 Perm: (1, 2, 0, 3) Sign: 1 Perm: (1, 2, 3, 0) Sign: -1 Perm: (1, 3, 2, 0) Sign: 1 Perm: (3, 1, 2, 0) Sign: -1 Perm: (3, 1, 0, 2) Sign: 1 Perm: (1, 3, 0, 2) Sign: -1 Perm: (1, 0, 3, 2) Sign: 1 Perm: (1, 0, 2, 3) Sign: -1