Permutations by swapping: Difference between revisions
m (→{{header|Python}}: Remove two links as they are in the task description) |
(→{{header|Python}}: Add Recursive version.) |
||
Line 12: | Line 12: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Python: iterative=== |
|||
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. |
||
Line 113: | Line 114: | ||
Perm: (1, 0, 3, 2) Sign: 1 |
Perm: (1, 0, 3, 2) Sign: 1 |
||
Perm: (1, 0, 2, 3) Sign: -1</pre> |
Perm: (1, 0, 2, 3) Sign: -1</pre> |
||
===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 [] |
|||
elif items == 1: |
|||
return [[0]] |
|||
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. |
Revision as of 18:51, 24 July 2012
Generate permutations of n items using algorithms based on swapping. 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.
- References
- Cf.
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>debug = False
def spermutations(n):
'permutations by swapping. Yields: perm, sign' sign = 1 lowest = [-1, 0, -1] # [num, direction, index] p = [[i, 0 if i==0 else -1, i] # [num, direction, index] for i in range(n)]
if debug: print ' #', p yield tuple(pp[0] for pp in p), sign while True: if all(pp[1] == 0 for pp in p): # Not moving break largest = max(p, key=lambda pp: pp if pp[1] else lowest) sign *= -1 n1, d1, i1 = largest if d1 == -1: # Swap down n2, d2, i2 = p[i1-1] p[i1] = [n2, d2, i1] p[i2] = [n1, d1, i2] # 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 n2, d2, i2 = p[i1+1] p[i1] = [n2, d2, i1] p[i2] = [n1, d1, i2] # 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 pp in p: n3, d3, i3 = 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>
- Sample 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 [] elif items == 1: return 0 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.