Permutations by swapping: Difference between revisions

Content added Content deleted
(Small improvements in the first Python entry)
Line 71: Line 71:
When saved in a file called spermutations.py it is used in the Python example to the [[Matrix arithmetic#Python|Matrix arithmetic]] task.
When saved in a file called spermutations.py it is used in the Python example to the [[Matrix arithmetic#Python|Matrix arithmetic]] task.


<lang python>debug = False
<lang python>from operator import itemgetter

DEBUG = False # like the built-in __debug__


def spermutations(n):
def spermutations(n):
'permutations by swapping. Yields: perm, sign'
"""permutations by swapping. Yields: perm, sign"""
sign = 1
sign = 1
p = [[i, 0 if i==0 else -1] # [num, direction]
p = [[i, 0 if i == 0 else -1] # [num, direction]
for i in range(n)]
for i in range(n)]


if debug: print ' #', p
if DEBUG: print ' #', p
yield tuple(pp[0] for pp in p), sign
yield tuple(pp[0] for pp in p), sign

while any(pp[1] for pp in p): # moving
while any(pp[1] for pp in p): # moving
i1, largest = max(((i, pp) for i, pp in enumerate(p) if pp[1]),
i1, (n1, d1) = max(((i, pp) for i, pp in enumerate(p) if pp[1]),
key=lambda x: x[1])
key=itemgetter(1))
n1, d1 = largest
sign *= -1
sign *= -1
if d1 == -1:
if d1 == -1:
# Swap down
# Swap down
i2 = i1-1
i2 = i1 - 1
p[i1], p[i2] = p[i2], p[i1]
p[i1], p[i2] = p[i2], p[i1]
# If this causes the chosen element to reach the First or last
# If this causes the chosen element to reach the First or last
# position within the permutation, or if the next element in the
# position within the permutation, or if the next element in the
# same direction is larger than the chosen element:
# same direction is larger than the chosen element:
if i2 == 0 or p[i2-1][0] > n1:
if i2 == 0 or p[i2 - 1][0] > n1:
# The direction of the chosen element is set to zero
# The direction of the chosen element is set to zero
p[i2][1] = 0
p[i2][1] = 0
elif d1 == 1:
elif d1 == 1:
# Swap up
# Swap up
i2 = i1+1
i2 = i1 + 1
p[i1], p[i2] = p[i2], p[i1]
p[i1], p[i2] = p[i2], p[i1]
# If this causes the chosen element to reach the first or Last
# If this causes the chosen element to reach the first or Last
# position within the permutation, or if the next element in the
# position within the permutation, or if the next element in the
# same direction is larger than the chosen element:
# same direction is larger than the chosen element:
if i2 == n-1 or p[i2+1][0] > n1:
if i2 == n - 1 or p[i2 + 1][0] > n1:
# The direction of the chosen element is set to zero
# The direction of the chosen element is set to zero
p[i2][1] = 0
p[i2][1] = 0
if debug: print ' #', p
if DEBUG: print ' #', p
yield tuple(pp[0] for pp in p), sign
yield tuple(pp[0] for pp in p), sign


Line 114: Line 115:
if n3 > n1:
if n3 > n1:
pp[1] = 1 if i3 < i2 else -1
pp[1] = 1 if i3 < i2 else -1
if debug: print ' # Set Moving'
if DEBUG: print ' # Set Moving'



if __name__ == '__main__':
if __name__ == '__main__':
Line 126: Line 127:
sp.add(i[0])
sp.add(i[0])
print('Perm: %r Sign: %2i' % i)
print('Perm: %r Sign: %2i' % i)
if debug: raw_input('?')
#if DEBUG: raw_input('?')
# Test
# Test
p = set(permutations(range(n)))
p = set(permutations(range(n)))
assert sp == p, 'Two methods of generating permutations do not agree'</lang>
assert sp == p, 'Two methods of generating permutations do not agree'</lang>
{{out}}

;Sample output:
<pre>Permutations and sign of 3 items
<pre>Permutations and sign of 3 items
Perm: (0, 1, 2) Sign: 1
Perm: (0, 1, 2) Sign: 1
Retrieved from "https://rosettacode.org/wiki/Permutations_by_swapping"