CODEWITHSUNDEEP
pythonrecursionpermutation
Ryan
Ryan

Reputation: 311

Permutations of a list of input numbers in Python

I'm supposed to write a program in Python that will get a list of numbers from the user until the user inputs 0, then print all the permutations of this list of numbers. I was working on the code, which seemed right at the begining, but for some reason I'm getting weird output.

It seems like the list is static, and every time the function returns it adds objects to the latest list. This doesn't happen the way it was before the function was called recursively.

Here is what I have so far:

    def permutation(numberList,array,place):
        if (place==len(numberList)):
            print array
        else:
            x=0
            while (x < len(numberList)):
                array.append(numberList[x])
                permutation(numberList,array,place+1)
                x+=1

    def scanList():
        numberList=[];
        number=input()
        #keep scanning for numbers for the list
        while(number!=0):
           numberList.append(number)
           number=input()
        return numberList

permutation(scanList(),[],0)

This is the output for the input 1 2 3 0, for example:

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

I would appreciate any help.

Upvotes: 1

Views: 956

Answers (2)

Kolmar
Kolmar

Reputation: 14224

The thing is, the list [] in Python is dynamic. So when you add elements to it with array.append(numberList[x]), they stay there forever. Just remove the added element after your recursive call:

def permutation(numberList,array,place):
    if (place==len(numberList)):
        print(array)
    else:
        x=0
        while (x < len(numberList)):
            array.append(numberList[x])
            permutation(numberList,array,place+1)
            array.pop()
            x+=1

That's actually the common way to write depth-first search algorithms: modify your structure, make recursive call, undo modifications. The result of your program doesn't seem to be permutations of the input though.

Upvotes: 1

Jakube
Jakube

Reputation: 3565

The Python way is to use itertools. 

from itertools import permutations
for permutation in permutations([1,2,3]):
    print(permutation)

Now whats wrong with your algorithm. As you noticed, the list is static (well not really, but your using the same list every time)

A simple fix would be to copy the list each time. 

def permutation(numberList,array,place):
    if (place==len(numberList)):
        print array
    else:
        x=0
        while (x < len(numberList)):
            array2 = array[:] // here happens the copy
            array2.append(numberList[x])
            permutation(numberList,array2,place+1)
            x+=1

Upvotes: 1

Related Questions