generate permutation of a list in python issue

Question

Below is the code I wrote to generate all permutations from a list.

def perm(arr):
 if len(arr)==1:
 return (arr)
 if len(arr)==0:
 return ([])
 else:
 result=[]
 for i in range(len(arr)):
 x=arr[i]
 xs=arr[:i]+arr[i+1:]
 for p in perm(xs):
 result.append([x]+p)
 return (result)
perm(['a', 'b', 'c'])

I got error below:

TypeError: can only concatenate list (not "str") to list

I spent a long time trying to figure out why, but I could not. Can anyone help with why above code give those error? Thanks a lot in advance.

• pythonic833: do you need this code to work or do you only want to get all permutations?

Answer 1

The problem is here:

if len(arr)==1:
 return (arr)

A list with only a single value only has one permutation - the list itself. But your function is supposed to return a list of permutations - in other words, a list of lists - so you have to wrap it in another list:

if len(arr)==1:
 return [arr]

Before the change, the result for single-element inputs wasn't a list of permutations, it was just a list of values:

>>> perm([1])
[1]

After the change, the result is correct:

>>> perm([1])
[[1]]

• zesla: if I use generator, it seems that I have to do: yield arr. I'm still kind of confused.... would you clarify me on that? @Aran-Fey
• Aran-Fey: @zesla Not without being able to see your code. You can/should ask a new question about that.

Answer 2

you can use itertools

import itertools
a = "123"
b = itertools.combinations(a,2)
for i in b:
 print i

your code is fine, just a small fix

result.append([x] + [i for i in p])

• zesla: I'm trying to practice programming instead of using existing tools @shahaf

Answer 3

The code can be cleaner if you just use strs, instead of lists:

def perm(arr):
 if len(arr) == 1:
 return arr
 if len(arr) == 0:
 return ""
 else:
 result = ""
 for i in range(len(arr)):
 x = arr[i]
 xs = arr[:i] + arr[i + 1:]
 for p in perm(xs):
 result.append(x + p)
 return result
print perm('abc')

['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

That solves the bug when appending the subproblem solutions too.

Answer 4

The problem is with parentheses.

return (arr) will return arr, not [arr].

return [arr] will fix the problem. Other parentheses in return also do nothing.