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.

do you need this code to work or do you only want to get all permutations? — pythonic833
– pythonic833, Commented Apr 5, 2018 at 15:34

Aran-Fey · Accepted Answer · 2018-04-05 15:57:12Z

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]]

answered Apr 5, 2018 at 15:57

Aran-Fey

44k13 gold badges113 silver badges161 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

zesla Over a year ago

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 Over a year ago

@zesla Not without being able to see your code. You can/should ask a new question about that.

shahaf · Accepted Answer · 2018-04-05 15:54:54Z

0

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])

edited Apr 5, 2018 at 15:54

answered Apr 5, 2018 at 15:37

shahaf

5,0132 gold badges32 silver badges35 bronze badges

1 Comment

zesla Over a year ago

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

carrdelling · Accepted Answer · 2018-04-05 15:56:53Z

0

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.

answered Apr 5, 2018 at 15:56

carrdelling

1,7351 gold badge18 silver badges17 bronze badges

Comments

graphite · Accepted Answer · 2018-04-05 16:02:13Z

0

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.

answered Apr 5, 2018 at 16:02

graphite

2,97024 silver badges42 bronze badges

Collectives™ on Stack Overflow

generate permutation of a list in python issue

4 Answers 4

2 Comments

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related