Permutations by swapping

Permutations by swapping is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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.

References

• Steinhaus–Johnson–Trotter algorithm
• Johnson-Trotter Algorithm Listing All Permutations

Cf.

• Matrix arithmetic

J

J has a built in mechanism for representing permutations (which is designed around the idea of selecting a permutation uniquely by an integer) but it does not seem seem to have an obvious mapping to Steinhaus–Johnson–Trotter. Perhaps someone with a sufficiently deep view of the subject of permutations can find a direct mapping?

Meanwhile, here's an inductive approach, using negative integers to look left and positive integers to look right:

<lang J>bfsjt0=: _1 - i. lookingat=: 0 >. <:@# <. i.@# + * next=: | >./@:* | > | {~ lookingat bfsjtn=: (((] <@, ] + *@{~) | i. next) C. ] * _1 ^ next < |)^:(*@next)</lang>

Here, bfsjt0 N gives the initial permutation of order N, and bfsjtn^:M bfsjt0 N gives the Mth Steinhaus–Johnson–Trotter permutation of order N. (bf stands for "brute force".)

To convert from the Steinhaus–Johnson–Trotter representation of a permutation to J's representation, use <:@|, or to find J's anagram index of a Steinhaus–Johnson–Trotter representation of a permutation, use A.<:@|

Example use:

<lang J> bfsjtn^:(i.!3) bfjt0 3 _1 _2 _3 _1 _3 _2 _3 _1 _2

3 _2 _1

_2 3 _1 _2 _1 3

  <:@| bfsjtn^:(i.!3) bfjt0 3

0 1 2 0 2 1 2 0 1 2 1 0 1 2 0 1 0 2

  A. <:@| bfsjtn^:(i.!3) bfjt0 3

0 1 4 5 3 2</lang>

Here's an example of the Steinhaus–Johnson–Trotter representation of 3 element permutation, with sign (sign is the first column):

<lang J> (_1^2|i.!3),. bfsjtn^:(i.!3) bfjt0 3

1 _1 _2 _3

_1 _1 _3 _2

1 _3 _1 _2

_1 3 _2 _1

1 _2  3 _1

_1 _2 _1 3</lang>

Alternatively, J defines C.!.2 as the parity of a permutation:

<lang J> (,.~C.!.2)<:| bfsjtn^:(i.!3) bfjt0 3

1 0 1 2

_1 0 2 1

1 2 0 1

_1 2 1 0

1 1 2 0

_1 1 0 2</lang>

Python

Python: iterative

When saved in a file called spermutations.py it is used in the Python example to the Matrix arithmetic task.

<lang python>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('Perm: %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'</lang>

Output:

Permutations and sign of 3 items
Perm: (0, 1, 2) Sign:  1
Perm: (0, 2, 1) Sign: -1
Perm: (2, 0, 1) Sign:  1
Perm: (2, 1, 0) Sign: -1
Perm: (1, 2, 0) Sign:  1
Perm: (1, 0, 2) Sign: -1

Permutations and sign of 4 items
Perm: (0, 1, 2, 3) Sign:  1
Perm: (0, 1, 3, 2) Sign: -1
Perm: (0, 3, 1, 2) Sign:  1
Perm: (3, 0, 1, 2) Sign: -1
Perm: (3, 0, 2, 1) Sign:  1
Perm: (0, 3, 2, 1) Sign: -1
Perm: (0, 2, 3, 1) Sign:  1
Perm: (0, 2, 1, 3) Sign: -1
Perm: (2, 0, 1, 3) Sign:  1
Perm: (2, 0, 3, 1) Sign: -1
Perm: (2, 3, 0, 1) Sign:  1
Perm: (3, 2, 0, 1) Sign: -1
Perm: (3, 2, 1, 0) Sign:  1
Perm: (2, 3, 1, 0) Sign: -1
Perm: (2, 1, 3, 0) Sign:  1
Perm: (2, 1, 0, 3) Sign: -1
Perm: (1, 2, 0, 3) Sign:  1
Perm: (1, 2, 3, 0) Sign: -1
Perm: (1, 3, 2, 0) Sign:  1
Perm: (3, 1, 2, 0) Sign: -1
Perm: (3, 1, 0, 2) Sign:  1
Perm: (1, 3, 0, 2) Sign: -1
Perm: (1, 0, 3, 2) Sign:  1
Perm: (1, 0, 2, 3) Sign: -1

Python: recursive

After spotting the pattern of highest number being inserted into each perm of lower numbers from right to left, then left to right, I developed this recursive function: <lang python>def spermutations(n):

   return [(tuple(item), -1 if i %2 else 1) for i, item in enumerate(sperm(n))]

def sperm(items):

   if items <= 0:
       return [[]]
   else:
       dir = 1
       new_items = []
       for item in sperm(items - 1):
           if dir == 1:
               # step down
               new_items += [item[:i] + [items-1] + item[i:] for i in range(len(item), -1, -1)]
           else:    
               # step up
               new_items += [item[:i] + [items-1] + item[i:] for i in range(len(item) + 1)]
           dir *= -1
       return new_items</lang>

Sample output

The output is the same as before except it is a list of all results rather than yielding each result from a generator function.