Permutations in Python without repetitions

Question

I am working on a program that gets a list as input from user and supposed to print all the permutations of the list. the thing is that the output I'm getting is with repetition of numbers from the list, So these are technically not really permutations. How can I avoid this? (notice that if a user inputs the same number twice in the list, this won't count as repetition) so basically I can't repeat the same index in every combination.

NB: I'm not allowed to use built in permutations functions.

This is what i've done so far:

def permutation(numberList,array,place):
    if (place==len(numberList)):
        print array
    else:
        i=0
        while (i < len(numberList)):
            array.append(numberList[i])
            permutation(numberList,array,place+1)
            array.pop()
            i+=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)

the output for 1 2 3 0 for example:

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

thanks.

what does it mean? what can i change in the code to do that? — Ryan, Jan 19 '15 at 23:14
Add each permutation as a tuple to a set and check the set each time. — Simeon Visser, Jan 19 '15 at 23:21
say your array has 3 elements. generate permutations of [0, 1, 2] (see http://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list-in-python). Then for every permutation P print numberList[P[0], P[1], P[2]]. do you get it? — mrk, Jan 19 '15 at 23:21

score 1 · Accepted Answer · answered Jan 20 '15 at 00:16

One simple solution is to use a set to know which numbers you already used and which ones you didn't:

def permutation(numberList,array,visited,place):
    if (place==len(numberList)):
        print array
    else:
        i=0
        while (i < len(numberList)):
            if i not in visited:
                visited.add(i)
                array.append(numberList[i])
                permutation(numberList,array,visited,place+1)
                array.pop()
                visited.remove(i)
            i+=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(),[],set(), 0)

Permutations in Python without repetitions

1 Answers1