Permutations by swapping: Difference between revisions

Content added Content deleted
(→‎{{header|Python}}: generalize it to a permutation of an arbitrary list, rather than just a range of numbers)
Line 216: Line 216:
DEBUG = False # like the built-in __debug__
DEBUG = False # like the built-in __debug__


def spermutations(n):
def spermutations(seq):
"""permutations by swapping. Yields: perm, sign"""
"""permutations by swapping. Yields: perm, sign"""
sign = 1
sign = 1
p = [[i, 0 if i == 0 else -1] # [num, direction]
p = [[x, 0 if i == 0 else -1] # [elem, direction]
for i in range(n)]
for i, x in enumerate(seq)]


if DEBUG: print ' #', p
if DEBUG: print ' #', p
Line 265: Line 265:
print '\nPermutations and sign of %i items' % n
print '\nPermutations and sign of %i items' % n
sp = set()
sp = set()
for i in spermutations(n):
for i in spermutations(range(n)):
sp.add(i[0])
sp.add(i[0])
print('Perm: %r Sign: %2i' % i)
print('Perm: %r Sign: %2i' % i)
Line 309: Line 309:
===Python: recursive===
===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:
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 s_permutations(n):
<lang python>def s_permutations(seq):
def s_perm(items):
def s_perm(seq):
if items <= 0:
if not seq:
return [[]]
return [[]]
else:
else:
new_items = []
new_items = []
for i, item in enumerate(s_perm(items - 1)):
for i, item in enumerate(s_perm(seq[:-1])):
if i % 2:
if i % 2:
# step down
# step down
new_items += [item[:i] + [items - 1] + item[i:]
new_items += [item[:i] + seq[-1:] + item[i:]
for i in range(len(item), -1, -1)]
for i in range(len(item), -1, -1)]
else:
else:
# step up
# step up
new_items += [item[:i] + [items - 1] + item[i:]
new_items += [item[:i] + seq[-1:] + item[i:]
for i in range(len(item) + 1)]
for i in range(len(item) + 1)]
return new_items
return new_items


return [(tuple(item), -1 if i % 2 else 1)
return [(tuple(item), -1 if i % 2 else 1)
for i, item in enumerate(s_perm(n))]</lang>
for i, item in enumerate(s_perm(seq))]</lang>


;Sample output:
;Sample output:
Line 334: Line 334:
===Python: Iterative version of the recursive===
===Python: Iterative version of the recursive===
Replacing the recursion in the example above produces this iterative version function:
Replacing the recursion in the example above produces this iterative version function:
<lang python>def s_permutations(n):
<lang python>def s_permutations(seq):
items = [[]]
items = [[]]
for j in range(n):
for j in seq:
new_items = []
new_items = []
for i, item in enumerate(items):
for i, item in enumerate(items):
Retrieved from "https://rosettacode.org/wiki/Permutations_by_swapping"