Anonymous user
Permutations by swapping: Difference between revisions
→{{header|Python}}: generalize it to a permutation of an arbitrary list, rather than just a range of numbers
(→{{header|Python}}: generalize it to a permutation of an arbitrary list, rather than just a range of numbers) |
|||
Line 216:
DEBUG = False # like the built-in __debug__
def spermutations(
"""permutations by swapping. Yields: perm, sign"""
sign = 1
p = [[
for i, x in
if DEBUG: print ' #', p
Line 265:
print '\nPermutations and sign of %i items' % n
sp = set()
for i in spermutations(range(n)):
sp.add(i[0])
print('Perm: %r Sign: %2i' % i)
Line 309:
===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 s_permutations(
def s_perm(
if
return [[]]
else:
new_items = []
for i, item in enumerate(s_perm(
if i % 2:
# step down
new_items += [item[:i] + seq[
for i in range(len(item), -1, -1)]
else:
# step up
new_items += [item[:i] + seq[
for i in range(len(item) + 1)]
return new_items
return [(tuple(item), -1 if i % 2 else 1)
for i, item in enumerate(s_perm(
;Sample output:
Line 334:
===Python: Iterative version of the recursive===
Replacing the recursion in the example above produces this iterative version function:
<lang python>def s_permutations(
items = [[]]
for j in
new_items = []
for i, item in enumerate(items):
| |||