Python: Permutations by swapping

Last update on December 21 2024 07:30:53 (UTC/GMT +8 hours)

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.