Permutation with recursion not printing all values in python?-CodePudding

I am writing python code to print all permutation of a number. Below is my code:

    a=[1,2,3,4]
    
    
    for i in range(len(a)):
    temp=a[:]
    temp[0],temp[i]=temp[i],temp[0]
    def p(temp,i):
        
        k=i 1
        if k ==len(a)-1:
            print(temp)
            return
        temp[k],temp[k 1]=temp[k 1],temp[k]

        p(temp,k)
        temp[k],temp[k 1]=temp[k 1],temp[k]
        p(temp,k)
    
 
    p(temp,i=0)

The idea is to replace every integer at first place and permutate remaining. That's what this for loop is doing:

    for i in range(len(a)):
        temp=a[:]
        temp[0],temp[i]=temp[i],temp[0]

But,for every permutation starting with i,it only prints 4 permutations. for ex: Starting with 1,the permutations should be:

[1,2,3,4]    
[1,2,4,3]    
[1,3,2,4]    
[1,3,4,2]    
[1,4,3,2]    
[1,4,2,3]

But,its only printing

[1,2,3,4]   
[1,2,4,3]  
[1,3,2,4]   
[1,3,4,2]

4 at second place is not getting printed. Missing:

[1,4,3,2]   
[1,4,2,3]

Can anyone tell me what am I doing wrong?

CodePudding user response：

Edited code:

def p(temp, k=0):
  
  if k == len(temp):
      print(temp)
      return

  for i in range(k, len(temp)):
     temp[k], temp[i] = temp[i], temp[k]
     p(temp, k 1)
     temp[k], temp[i] = temp[i], temp[k]

p([1,2,3,4])

result:

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 3, 2]
[1, 4, 2, 3]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 3, 1]
[2, 4, 1, 3]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 2, 3, 1]
[4, 2, 1, 3]
[4, 3, 2, 1]
[4, 3, 1, 2]
[4, 1, 3, 2]
[4, 1, 2, 3]

CodePudding user response：

Heres a correction for your process

a=[1,2,3,4]

def p(temp,i):

    k=i 1
    if k ==len(a)-1:
        print(temp)
        return
    temp[k],temp[k 1]=temp[k 1],temp[k]
    prev = temp.copy()


    p(temp,k)
    temp[k],temp[k 1]=temp[k 1],temp[k]
    p(temp,k)
    temp[k],temp[k 1]=temp[k 1],temp[k]
    if temp != prev:
        p(temp,k)

for i in range(len(a)):
    temp=a[:]
    temp[0],temp[i]=temp[i],temp[0]
    p(temp,i=0)

The problem was that you were only rearranging the temp list 2 times in the actual call of the function p from the for loop. Calling it three times made it to contain '4' in the second place of the permutation. The if statement I added is to check if the previous rearranged temp is not the as the current rearrange temp, this removed duplicate results which occurred when calling the function p three times. Although I do recommend Hamid's answer.

CodePudding user response：

The logic seems to be wrong. You are swapping the neighboring elements. Because of that, you are unable to generate all the permutations. Ideally, you want to recursively repeat the logic of fixing the first element.