Python: Permutations by swapping - w3resource
w3resource

Python: Permutations by swapping

Python Itertools: Exercise-18 with Solution

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

Python Code Editor:


Have another way to solve this solution? Contribute your code (and comments) through Disqus.

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.

What is the difficulty level of this exercise?

Test your Python skills with w3resource's quiz

Python: Tips of the Day