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:
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.