Permutations of a list of input numbers in Python

Question

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.

possible duplicate of [How to generate all permutations of a list in Python](http://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list-in-python) — mbomb007, Jan 19 '15 at 21:55

Jakube · Answer 1 · 2015-01-19T21:49:45.657

1

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

edited Jan 19 '15 at 21:49

answered Jan 19 '15 at 21:42

Jakube

3,353
3
23
40

if i was allowed to do that i would've done that already, the thing is, it's homework. thanks though. – Ryan Jan 19 '15 at 21:44
@Ryan if this isn't about using Python, maybe tag with [tag:algorithms]. – Peter Wood Jan 19 '15 at 21:52

score 1 · Accepted Answer · answered Jan 19 '15 at 21:50

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.

you're right, it's not, i just realized that permutation shouldn't repeat numbers. wondering what went wrong. as for the answer, works perfect! — Ryan, Jan 19 '15 at 21:53

Permutations of a list of input numbers in Python

2 Answers2