Python: Permutations by swapping
18. Swapping Successive Permutations
Write a Python program to generate permutations of n items in which successive permutations differ from each other by the swapping of any two items.
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.
Show the permutations and signs of three items, in order of generation here.
Such data are of use in generating the determinant of a square matrix and any functions created should bear this in mind.
Note: The Steinhaus–Johnson–Trotter algorithm generates successive permutations where adjacent items are swapped, but from this discussion adjacency is not a requirement.
Source: https://bit.ly/36KKbHo
Sample Solution:
Python Code:
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('Permutation: %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'
Sample Output:
Permutations and sign of 3 items Permutation: (0, 1, 2) Sign: 1 Permutation: (0, 2, 1) Sign: -1 Permutation: (2, 0, 1) Sign: 1 Permutation: (2, 1, 0) Sign: -1 Permutation: (1, 2, 0) Sign: 1 Permutation: (1, 0, 2) Sign: -1 Permutations and sign of 4 items Permutation: (0, 1, 2, 3) Sign: 1 Permutation: (0, 1, 3, 2) Sign: -1 Permutation: (0, 3, 1, 2) Sign: 1 Permutation: (3, 0, 1, 2) Sign: -1 Permutation: (3, 0, 2, 1) Sign: 1 Permutation: (0, 3, 2, 1) Sign: -1 Permutation: (0, 2, 3, 1) Sign: 1 Permutation: (0, 2, 1, 3) Sign: -1 Permutation: (2, 0, 1, 3) Sign: 1 Permutation: (2, 0, 3, 1) Sign: -1 Permutation: (2, 3, 0, 1) Sign: 1 Permutation: (3, 2, 0, 1) Sign: -1 Permutation: (3, 2, 1, 0) Sign: 1 Permutation: (2, 3, 1, 0) Sign: -1 Permutation: (2, 1, 3, 0) Sign: 1 Permutation: (2, 1, 0, 3) Sign: -1 Permutation: (1, 2, 0, 3) Sign: 1 Permutation: (1, 2, 3, 0) Sign: -1 Permutation: (1, 3, 2, 0) Sign: 1 Permutation: (3, 1, 2, 0) Sign: -1 Permutation: (3, 1, 0, 2) Sign: 1 Permutation: (1, 3, 0, 2) Sign: -1 Permutation: (1, 0, 3, 2) Sign: 1 Permutation: (1, 0, 2, 3) Sign: -1
For more Practice: Solve these Related Problems:
- Write a Python program to generate permutations of n items where each successive permutation differs by a swap of two elements.
- Write a Python program to create an iterator that generates successive permutations by swapping adjacent elements using itertools.
- Write a Python program to produce permutations that differ by a single transposition and then verify that all adjacent pairs differ by exactly two elements.
- Write a Python program to generate a list of permutations where each permutation is derived from the previous one by swapping any two items, ensuring minimal change.
Go to:
Previous: Write a Python program to read a given string character by character and compress repeated character by storing the length of those character(s).
Next: Write a Python program which iterates the integers from 1 to a given number and print "Fizz" for multiples of three, print "Buzz" for multiples of five, print "FizzBuzz" for multiples of both three and five using itertools module.
Python Code Editor:
Have another way to solve this solution? Contribute your code (and comments) through Disqus.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.