Python permutations recursive

0
votes

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?

2
pythonalgorithmrecursionpermutationbacktracking
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. – PM 2Ring

2 Answers

2
votes

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]
1
votes

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]