Python permutations recursive

Question

I'm trying to solve a problem using backtracking and I need the permutations of numbers for it. I have this basic algorithm that does it but the problem is... the results don't come in the normal order.

def perm(a,k=0):
 if(k==len(a)):
 print(a)
 else:
 for i in range(k,len(a)):
 a[k],a[i] = a[i],a[k]
 perm(a, k+1)
 a[k],a[i] = a[i],a[k]

Example: for [1,2,3] the normal results would be: [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]

Whereas this algorithm will interchange the last 2 elements. I understand why. I just don't know how to correct this.

I don't want to use the permutations from itertools. Can the code above be easily fixed to work properly? What would be the complexity for this algorithm from above?

• PM 2Ring: Here's some non-recursive code that uses an ancient algorithm of Narayana Pandita to produce permutations in lexicographic order (assuming the initial list is sorted correctly): stackoverflow.com/a/31678111/4014959
• PM 2Ring: You may also find stackoverflow.com/a/28525468/4014959 of interest: it can produce any permutation from an index number.

Answer 1

A recursive generator function that yields permutations in the expected order with regard to the original list:

def perm(a):
 if len(a) <= 1:
 yield a
 else:
 for i in xrange(len(a)):
 for p in perm(a[:i]+a[i+1:]):
 yield [a[i]]+p
a = [1, 2, 3]
for p in perm(a):
 print(p)
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Answer 2

Here's one (suboptimal, because copying lists all the time) solution:

def perm(a, prev=[]):
 if not a:
 print(prev)
 for index, element in enumerate(a):
 perm(a[:index] + a[index+1:], prev + [element])

‌The order it is printed out:

>>> perm([1,2,3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Answer 3

Let's say you have five elements ABCDE and you're in the top call, i.e., selecting the first element and recursing for permuting the remaining four. Your loop and swaps produce these:

ABCDE (selected A as first, permute BCDE recursively)
BACDE
CBADE (selected C as first, permute BADE recursively)
DBCAE
EBCDA

While the first position correctly goes through A to E, the remaining four aren't always in the original order. For example BADE instead of ABDE. What you want instead is these:

ABCDE
BACDE
CABDE
DABCE
EABCD

You can see that you get from one to the next with a single swap. Namely your a[k],a[i] = a[i],a[k] before the recursion. So remove your swap after the recursion. Instead restore the original order after the loop, by moving the E all the way back to the end:

def perm(a,k=0):
 if(k==len(a)):
 print(a)
 else:
 for i in range(k,len(a)):
 a[k],a[i] = a[i],a[k]
 perm(a, k+1)
 a.append(a.pop(k))
perm([*'123'])

Attempt This Online!

Answer 4

Interesting problem. Your approach is very efficient, with complexity O(n!*n), because it only swaps elements (no list copy, pop, insert, etc of O(n) complexity used) but the lexicographical order is lost. One easy way to keep the order is to sort the indices, but this is not efficient, with complexity O(n!*nlogn):

def perm(a,k=0):
 if k == len(a):
 print(a)
 else:
 sorted_indices = sorted(range(k, len(a)), key=lambda x: a[x])
 for i in sorted_indices:
 a[k],a[i] = a[i],a[k]
 perm(a, k+1)
 a[k],a[i] = a[i],a[k]
perm([1,2,3])

The best way I can think of is this, with complexity O(n!*n):

class Indices_List:
 """ List of indices 0,1,...,n that can be swapped.
 'sorted' keeps for each value at what index it is stored in 'indices'. 
 """
 def __init__(self, n):
 self.indices = [i for i in range(n)]
 self.sorted = self.indices.copy()
 def __repr__(self):
 return str(self.indices) + '\n' + str(self.sorted)
 def __len__(self):
 return len(self.indices)
 def get_indices(self):
 return self.indices
 
 def get_sorted(self):
 return self.sorted
 def swap(self, i, j):
 self.sorted[self.indices[i]] = j
 self.sorted[self.indices[j]] = i
 self.indices[i], self.indices[j] = self.indices[j], self.indices[i]
def perm(il, k=0):
 if k == len(il):
 yield il.get_indices()
 else:
 for i in il.get_sorted():
 if i >= k:
 il.swap(k, i)
 yield from perm(il, k+1)
 il.swap(k, i)
def get_permutation(values, indices):
 return [values[i] for i in indices]
 
values = ['a','b','c','d'] 
for p in perm(Indices_List(len(values))):
 print(get_permutation(values, p))

with this output in lexicographical order:

['a', 'b', 'c', 'd']
['a', 'b', 'd', 'c']
['a', 'c', 'b', 'd']
['a', 'c', 'd', 'b']
['a', 'd', 'b', 'c']
...
['d', 'a', 'c', 'b']
['d', 'b', 'a', 'c']
['d', 'b', 'c', 'a']
['d', 'c', 'a', 'b']
['d', 'c', 'b', 'a']

I read that the Steinhaus–Johnson–Trotter algorithm does it faster, but doesn't give lexicographical order.