Permutations: Difference between revisions

(0, 1, 2)

(0, 2, 1)

(1, 0, 2)

(1, 2, 0)

(2, 0, 1)

(2, 1, 0)</lang>

== Iterative implementation ==

Given a permutation, one can easily compute the ''next'' permutation in some ordre, for example lexicographic order, here. Then to get all permutations, it's enough to start from [0, 1, ... n-1], and store the next permutation until [n-1, n-2, ... 0], which is the last in lexicographic order.

<lang python>def nextperm(a):

n = len(a)

i = n - 1

while i > 0 and a[i - 1] > a[i]:

i -= 1

j = i

k = n - 1

while j < k:

a[j], a[k] = a[k], a[j]

j += 1

k -= 1

if i == 0:

return False

else:

j = i

while a[j] < a[i - 1]:

j += 1

a[i - 1], a[j] = a[j], a[i - 1]

return True

def perm3(n):

if type(n) is int:

if n < 1:

return []

a = list(range(n))

else:

a = sorted(n)

u = [tuple(a)]

while nextperm(a):

u.append(tuple(a))

return u

for p in perm3(3): print(p)