Anonymous user
Permutations: Difference between revisions
→{{header|Python}}: python implementation, recursive
(→{{header|Python}}: python implementation, recursive) |
|||
Line 2,955:
(3, 2, 1)
</pre>
=== Recursive implementation ===
The follwing functions start from a list [0 ... n-1] and exchange elements to always have a valid permutation. This is done recursively: first exchange a[0] with all the other elements, then a[1] with a[2] ... a[n-1], etc. thus yielding all permutations.
<lang python>def perm1(n):
a = list(range(n))
def sub(i):
nonlocal a
if i == n - 1:
yield tuple(a)
else:
for k in range(i, n):
a[i], a[k] = a[k], a[i]
yield from sub(i + 1)
a[i], a[k] = a[k], a[i]
yield from sub(0)
def perm2(n):
a = list(range(n))
def sub(i):
nonlocal a
if i == n - 1:
yield tuple(a)
else:
for k in range(i, n):
a[i], a[k] = a[k], a[i]
yield from sub(i + 1)
x = a[i]
for k in range(i + 1, n):
a[k - 1] = a[k]
a[n - 1] = x
yield from sub(0)</lang>
These two solutions make use of a generator, and "yield from" introduced in [https://www.python.org/dev/peps/pep-0380/ PEP-380]. They are slightly different: the latter produces permutations in lexicographic order, because the "remaining" part of a (that is, a[i:]) is always sorted, whereas the former always reverses the exchange just after the recursive call.
<lang python>for u in perm1(3): print(u)
(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
(1, 2, 0)
(2, 1, 0)
(2, 0, 1)
for u in perm2(3): print(u)
(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)</lang>
=={{header|Qi}}==
| |||