CODEWITHSUNDEEP
pythonalgorithmrecursion
fuzzycuffs
fuzzycuffs

Reputation: 139

Generate Permutation in Lexicographic Order using Recursion

I'm doing project euler q24, but this snippet of code that generates permutations doesn't work as expected. I'm not sure how to explain the logic of the code, but it uses recursion to create every set of permutations at a certain index then moves onto the next index. 

def genPermutation(num,index):
    if (index == (len(num)-1)):
        print(num)
    else:
        i = 0
        while i<(len(num)-index):
            newList = num
            temp = newList[index+i]
            newList.pop(index+i)
            newList.insert(index,temp)
            genPermutation(newList,index+1)
            i = i+1

a = [0,1,2,3,4,5]
genPermutation(a,0)

Upvotes: 0

Views: 1506

Answers (1)

AChampion
AChampion

Reputation: 30258

Your major flaw is that assigning a list does not create a new list, when you recurse down you are changing the same list as further up in the call stack, so you are getting duplicates and strange ordering.
You need:

newList = num[:]   # Create a new list

However, you've also got a few unnecessaries. A) You don't need a while loop, B) You don't need an index and a pop:

def genPermutation(num,index):
    if index == len(num)-1:
        print(num)
        return

    for i in range(index, len(num)):
        newList = num[:]
        temp = newList.pop(i)
        newList.insert(index, temp)
        genPermutation(newList, index+1)

Gives you the full list without duplicates:

>>> a = list(range(6))
>>> genPermutation(a,0))
[[0, 1, 2, 3, 4, 5],
 [0, 1, 2, 3, 5, 4],
 [0, 1, 2, 4, 3, 5],
 [0, 1, 2, 4, 5, 3],
 [0, 1, 2, 5, 3, 4],
 [0, 1, 2, 5, 4, 3],
 [0, 1, 3, 2, 4, 5],
 [0, 1, 3, 2, 5, 4],
 ...

However, this whole approach is very inefficient. Using recursion with all these list creations is very expensive when compared to a iterative approach, see the implementation of itertools.permutation()

Upvotes: 1

Related Questions