Using recursion to find all permutations of a list in Python

Question

So I am aware this topic has been covered. However, I am having troubles with my own implementation of it.

    def permutation(word, fixed = [], passed = ""):
        if passed != "":
            fixed.append(passed)

        if len(word) == 1:
            fixed.append(word[0])
            print fixed
        else:
            for i in range(len(word)):
                passed = word[i]
                rem = word[:i] + word[i+1:]
                permutation(rem, fixed, passed)

    permutation(["a","b","c"])
    raw_input()

I am trying not to have return values but instead get to the base and then print the result. Although when I do this I get the following:

    ['a', 'b', 'c']
    ['a', 'b', 'c', 'c', 'b']
    ['a', 'b', 'c', 'c', 'b', 'b', 'a', 'c']
    ['a', 'b', 'c', 'c', 'b', 'b', 'a', 'c', 'c', 'a']
    ['a', 'b', 'c', 'c', 'b', 'b', 'a', 'c', 'c', 'a', 'c', 'a', 'b']
    ['a', 'b', 'c', 'c', 'b', 'b', 'a', 'c', 'c', 'a', 'c', 'a', 'b', 'b', 'a']

This seems to be close, however, I can tell that fixed is collecting all of the outputs and I don't fully understand why.

When using recursion are each set of variables local to that call of the function? It is my understanding that is the case but it doesn't really seem to be here.

This is not homework btw.

Updated code for anybody interested:

    def permutation(word, fixed = "", passed = ""):
        if passed != "":
            fixed += passed

        if len(word) == 1:
            fixed += word[0]
            print fixed
        else:
            for i in range(len(word)):
                passed = word[i]
                rem = word[:i] + word[i+1:]
                permutation(rem, fixed, passed)

    permutation(["a","b","c"])
    raw_input()

Which produces the output: abc acb bac bca cab cba

If it is not a homework why not [`itertools.permutations`](http://docs.python.org/2/library/itertools.html#itertools.permutations)? — thefourtheye, Feb 16 '14 at 02:55

score 0 · Accepted Answer · edited May 23 '17 at 11:50

0

Your function is passed a reference to the list fixed, so your function can mutate it. The accepted answer to this question has a great explanation.

edited May 23 '17 at 11:50

Community

1
1

answered Feb 16 '14 at 02:47

highlycaffeinated

19,729
9
60
91

I edited my code to use only strings after reading that. Many thanks dude! – Josh Feb 16 '14 at 03:34

score 0 · Answer 2 · answered Mar 06 '23 at 21:23

Use this code

def get_permutations(sequence):

ls = []
if len(sequence) <= 1:
    ls.append(sequence)
else:
    ls = merge(sequence[0], get_permutations(sequence[1:]))
return ls

def merge(ch, sequence):

lst = []
for i in sequence:
    for j in range(len(i)+1):
        lst.append(i[0:j] + ch + i[j:])
return lst

if name == 'main':

input = 'abcd'
print(get_permutations(input))

Using recursion to find all permutations of a list in Python

2 Answers2