Recursive list comprehension for permutation. Python

Question

i have a function in python, which is programmed recursive in a list comprehension. But i don't understand it clearly what really happens in it!

def permut(s,l):
    if l == []: return [[s]]
    return [ e + [l[0]] for e in permut(s, l[1:])] + [l+[s]]

The function gets two arguments, firstly a String and the second a list and it returns the permutation of the String in the list.

permut('a', [1,2,3])
[['a', 3, 2, 1], [3, 'a', 2, 1], [2, 3, 'a', 1], [1, 2, 3, 'a']]

Can someone explain, what happens in the list comprehension?

What are you really trying to do? Is it your own code? If not, are you trying to fix something wrong with it, or simply understand it? — Karl Knechtel
– Karl Knechtel, Commented Apr 16, 2013 at 9:50
I want to understand, what happens in the list comprehension exactly? — Oni1
– Oni1, Commented Apr 16, 2013 at 12:06

Tim Pietzcker · Accepted Answer · 2013-04-16 08:00:58Z

3

If the list comprehension syntax is throwing you off, you can rewrite this function as follows and add some debug print()s along the way:

def permut(s,l):
    print("Entering function permut()")
    print("Parameters:\ns: {}\nl: {}".format(s,l))
    if l == []: 
        print("End of recursion reached, returning {}".format([[s]]))
        return [[s]]
    result = []
    for e in permut(s, l[1:]):
        result.append(e + [l[0]])
    result += [l + [s]]
    print("Returning {}".format(result))
    return result

This is the output you get:

>>> permut('a', [1,2,3])
Entering function permut()
Parameters:
s: a
l: [1, 2, 3]
Entering function permut()
Parameters:
s: a
l: [2, 3]
Entering function permut()
Parameters:
s: a
l: [3]
Entering function permut()
Parameters:
s: a
l: []
End of recursion reached, returning [['a']]
Returning [['a', 3], [3, 'a']]
Returning [['a', 3, 2], [3, 'a', 2], [2, 3, 'a']]
Returning [['a', 3, 2, 1], [3, 'a', 2, 1], [2, 3, 'a', 1], [1, 2, 3, 'a']]
[['a', 3, 2, 1], [3, 'a', 2, 1], [2, 3, 'a', 1], [1, 2, 3, 'a']]

edited Apr 16, 2013 at 8:00

answered Apr 16, 2013 at 7:21

Tim Pietzcker

337k59 gold badges520 silver badges572 bronze badges

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

2 Comments

Oni1 Over a year ago

Not really, what takes the variable e for a value always??

Verena Praher Over a year ago

@T.C. it iterates over the return value of permut(s, l[1:]), meaning first it is ['a', 3, 2, 1], then [3, 'a', 2, 1], ... (using the example you provided in the question)

TNW · Accepted Answer · 2013-04-16 07:42:36Z

2

First of all, you have a instead of s in recursive permut call.

return [ e + [l[0]] for e in permut(a, l[1:])] + [l+[s]]

First, it calculates permut(s, l[1:]), that is: tries to permute s and the part of the list without the first element. It throws the first element away as long there's any, then the recursive call returns [[s]].

Now, going backwards in calls, s is "added" to the every element of recursively created list, then given l is appended, and the results are:

# l == []
return [['a']]

# e == ['a']
# l == [3], l[0] == 3
return [['a'] + [3]] + [[3] + [a]]
# equals [['a', 3], [3, 'a']]

# e == ['a', 3] then [3, 'a']
# l == [2, 3], l[0] == 2
return [['a', 3] + [2], [3, 'a'] + [2]] + \
        [[2, 3] + [a]]
# equals [['a', 3, 2], [3, 'a', 2], [2, 3, 'a']]

# e == ['a', 3, 2] then [3, 'a', 2] then [2, 3, 'a']
# l == [1, 2, 3], l[0] == 1
return [['a', 3, 2] + [1], [3, 'a', 2] + [1], [2, 3, 'a'] + [1]] + \
        [[1, 2, 3] + ['a']]
# equals [['a', 3, 2, 1], [3, 'a', 2, 1], [2, 3, 'a', 1], [1, 2, 3, 'a']]

Maybe it's not beautiful to read, but it kind of works. You can see that e is extracted as single element of the list returned on the previous level.

You could also try:

def tee(parm):
    print parm
    return parm

And redefine permut as:

def permut(s,l):
    if l == []: return [[s]]
    return [ e + [l[0]] for e in tee(permut(s, l[1:]))] + [l+[s]]

My output:

[['a']]
[['a', 3], [3, 'a']]
[['a', 3, 2], [3, 'a', 2], [2, 3, 'a']]
[['a', 3, 2, 1], [3, 'a', 2, 1], [2, 3, 'a', 1], [1, 2, 3, 'a']]

Which covers recursive calls.

answered Apr 16, 2013 at 7:42

TNW

7266 silver badges15 bronze badges

1 Comment

TNW Over a year ago

To calculate permut('a', [1, 2, 3]) permut('a', [2, 3]) needs to be calculated first. In it, permut('a', [3]) is called, which calls permut('a', []). This way, permut('a', []) is the first call which has everything it needs to return a value, so it returns it to the higher level, which in turn is able to calculate the return value, too - and so it goes - forward in calls, backwards in returning results. It's possible to not go backwards with "tail recursion", though - I encourage you to explore this topic (though it's not much Python relevant).

Collectives™ on Stack Overflow

Recursive list comprehension for permutation. Python

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related