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 · Accepted Answer · 2022-08-21 07:22:23Z

1

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]

edited Aug 21, 2022 at 7:22

answered Aug 21, 2022 at 6:58

Hamid Rasti

9951 gold badge8 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Ibrahim · Accepted Answer · 2022-08-21 07:17:29Z

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.

Gaurav · Accepted Answer · 2022-08-21 07:18:40Z

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, 2022 at 7:18

Gaurav

1191 silver badge4 bronze badges

1 Comment

Community Over a year ago

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.

Collectives™ on Stack Overflow

Permutation with recursion not printing all values in python?

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related