Permutations by swapping: Difference between revisions
Small improvements in the first Python entry |
|||
Line 71: | Line 71: | ||
When saved in a file called spermutations.py it is used in the Python example to the [[Matrix arithmetic#Python|Matrix arithmetic]] task. |
When saved in a file called spermutations.py it is used in the Python example to the [[Matrix arithmetic#Python|Matrix arithmetic]] task. |
||
<lang python> |
<lang python>from operator import itemgetter |
||
DEBUG = False # like the built-in __debug__ |
|||
def spermutations(n): |
def spermutations(n): |
||
"""permutations by swapping. Yields: perm, sign""" |
|||
sign = 1 |
sign = 1 |
||
p = [[i, 0 if i==0 else -1] |
p = [[i, 0 if i == 0 else -1] # [num, direction] |
||
for i in range(n)] |
for i in range(n)] |
||
if |
if DEBUG: print ' #', p |
||
yield tuple(pp[0] for pp in p), sign |
yield tuple(pp[0] for pp in p), sign |
||
while any(pp[1] for pp in p): # moving |
while any(pp[1] for pp in p): # moving |
||
i1, |
i1, (n1, d1) = max(((i, pp) for i, pp in enumerate(p) if pp[1]), |
||
key= |
key=itemgetter(1)) |
||
n1, d1 = largest |
|||
sign *= -1 |
sign *= -1 |
||
if d1 == -1: |
if d1 == -1: |
||
# Swap down |
# Swap down |
||
i2 = i1-1 |
i2 = i1 - 1 |
||
p[i1], p[i2] = p[i2], p[i1] |
p[i1], p[i2] = p[i2], p[i1] |
||
# If this causes the chosen element to reach the First or last |
# If this causes the chosen element to reach the First or last |
||
# position within the permutation, or if the next element in the |
# position within the permutation, or if the next element in the |
||
# same direction is larger than the chosen element: |
# same direction is larger than the chosen element: |
||
if i2 == 0 or p[i2-1][0] > n1: |
if i2 == 0 or p[i2 - 1][0] > n1: |
||
# The direction of the chosen element is set to zero |
# The direction of the chosen element is set to zero |
||
p[i2][1] = 0 |
p[i2][1] = 0 |
||
elif d1 == 1: |
elif d1 == 1: |
||
# Swap up |
# Swap up |
||
i2 = i1+1 |
i2 = i1 + 1 |
||
p[i1], p[i2] = p[i2], p[i1] |
p[i1], p[i2] = p[i2], p[i1] |
||
# If this causes the chosen element to reach the first or Last |
# If this causes the chosen element to reach the first or Last |
||
# position within the permutation, or if the next element in the |
# position within the permutation, or if the next element in the |
||
# same direction is larger than the chosen element: |
# same direction is larger than the chosen element: |
||
if i2 == n-1 or p[i2+1][0] > n1: |
if i2 == n - 1 or p[i2 + 1][0] > n1: |
||
# The direction of the chosen element is set to zero |
# The direction of the chosen element is set to zero |
||
p[i2][1] = 0 |
p[i2][1] = 0 |
||
if |
if DEBUG: print ' #', p |
||
yield tuple(pp[0] for pp in p), sign |
yield tuple(pp[0] for pp in p), sign |
||
Line 114: | Line 115: | ||
if n3 > n1: |
if n3 > n1: |
||
pp[1] = 1 if i3 < i2 else -1 |
pp[1] = 1 if i3 < i2 else -1 |
||
if |
if DEBUG: print ' # Set Moving' |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
Line 126: | Line 127: | ||
sp.add(i[0]) |
sp.add(i[0]) |
||
print('Perm: %r Sign: %2i' % i) |
print('Perm: %r Sign: %2i' % i) |
||
if |
#if DEBUG: raw_input('?') |
||
# Test |
# Test |
||
p = set(permutations(range(n))) |
p = set(permutations(range(n))) |
||
assert sp == p, 'Two methods of generating permutations do not agree'</lang> |
assert sp == p, 'Two methods of generating permutations do not agree'</lang> |
||
{{out}} |
|||
;Sample output: |
|||
<pre>Permutations and sign of 3 items |
<pre>Permutations and sign of 3 items |
||
Perm: (0, 1, 2) Sign: 1 |
Perm: (0, 1, 2) Sign: 1 |
Revision as of 14:46, 28 July 2012
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
- Cf.
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.