Permutation with recursion not printing all values in python?

Question

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?

Hamid Rasti · Answer 1 · 2022-08-21T07:22:23.577

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]

score 0 · Answer 2 · answered Aug 21 '22 at 07:17

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.

score 0 · Answer 3 · answered Aug 21 '22 at 07:18

0

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.

answered Aug 21 '22 at 07:18

Gaurav

59
1
2

Your answer could be improved with additional supporting information. Please [edit] to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Community Aug 25 '22 at 05:28

Permutation with recursion not printing all values in python?

3 Answers3