Python beginner confused by a complex line of code

Question

I understand the gist of the code, that it forms permutations; however, I was wondering if someone could explain exactly what is going on in the return statement.

def perm(l):
    sz = len(l)
    print (l)
    if sz <= 1:
        print ('sz <= 1')
        return [l]
    return [p[:i]+[l[0]]+p[i:] for i in range(sz) for p in perm(l[1:])]

Answer 1

Okay, let's begin.

Starting code

(minus print statements)

def perm(l):
    sz = len(l)
    if sz <= 1:
        return [l]
    return [p[:i]+[l[0]]+p[i:] for i in range(sz) for p in perm(l[1:])]

Revision 1

def perm(s):
    # Base case: an empty list or a list with only one item has only one
    # permutation
    if len(s) <= 1:
        return [s]
    return [p[:i] + [s[0]] + p[i:]
            for i in range(len(s)) for p in perm(s[1:])]

• Rename l to s
• Remove sz, instead using len(s) directly. We might lose a tiny bit of efficiency, but we gain a huge amount of readability
• Fix spacing in list comprehension

Revision 2

def perm(s):
    # Base case: an empty list or a list with only one item has only one
    # permutation
    if len(s) <= 1:
        return [s]

    # A list of permutations
    permutations = []
    for i in range(len(s)):
        # Recursively find all permutations of s[1:]
        for p in perm(s[1:]):
            # Insert s[0] in position i
            permutations.append(p[:i] + [s[0]] + p[i:])
    return permutations

• Break apart the list comprehension

Revision 3

def perm(s):
    # Base case: an empty list or a list with only one item has only one
    # permutation
    if len(s) <= 1:
        return [s]

    # A list of permutations
    permutations = []
    # Recursively find all permutations of s[1:]
    for p in perm(s[1:]):
        for i in range(len(s)):
            # Insert s[0] in position i
            permutations.append(p[:i] + [s[0]] + p[i:])
    return permutations

• Change the nesting of the for loops. Now, you can say: for each permutation, take each position i, and add a copy of that permutation with s[0] inserted in each position i. This gets clearer in the next few revisions.

Revision 4

def perm(s):
    # Base case: an empty list or a list with only one item has only one
    # permutation
    if len(s) <= 1:
        return [s]

    # Recursively find all permutations of s[1:]
    shortperms = perm(s[1:])
    # A list of permutations
    permutations = []
    for shortperm in shortperms:
        for i in range(len(s)):
            # Make a copy of shortperm
            spcopy = shortperm[:]
            # Insert s[0] in position i
            spcopy.insert(s[0], i)
            # Add this to the list of permutations
            permutations.append(spcopy)
    return permutations

• Moved the perm function call. Now, the shortperms variable will contain all the permutations of s[1:], which is s minus the first item.
• Changed the list addition into three operations:
  • Make a copy of shortperm
  • Insert the first item in s
  • Add that list to permutations

Revision 5

def perm(s):
    # Base case: an empty list or a list with only one item has only one
    # permutation
    if len(s) <= 1:
        return [s]

    # Recursively find all permutations of s[1:]
    shortperms = perm(s[1:])
    # A list of permutations
    permutations = []
    for shortperm in shortperms:
        for i in range(len(shortperm) + 1):
            # Make a copy of shortperm
            spcopy = shortperm[:]
            # Insert s[0] in position i
            spcopy.insert(s[0], i)
            # Add this to the list of permutations
            permutations.append(spcopy)
    return permutations

• len(s) is the same as len(shortperm) + 1, because each shortperm is a permutation of the items in s, minus the first one. However, this is probably more readable.

Final code

With a docstring comment

def perm(s):
    """Return a list of all permutations of the items in the input
    sequence."""
    # Base case: an empty list or a list with only one item has only one
    # permutation
    if len(s) <= 1:
        return [s]

    # Recursively find all permutations of s[1:]
    shortperms = perm(s[1:])
    # A list of permutations
    permutations = []
    for shortperm in shortperms:
        for i in range(len(shortperm) + 1):
            # Make a copy of shortperm
            spcopy = shortperm[:]
            # Insert s[0] in position i
            spcopy.insert(s[0], i)
            # Add this to the list of permutations
            permutations.append(spcopy)
    return permutations

Answer 2

There are a couple of examples in the Python documentation for the itertools.permutations() function that are easier to digest. Note that this function is new in Python 2.6, so it won't be available for you if you're using anything older.

There are also many examples and explanations in SO conversations that have already occurred in the not-too-distant past that also represent good reading:

algorithm for python itertools.permutations

How to generate all permutations of a list in Python

Answer 3

This return is returning a list comprehension whose items are made by inserting the first item of l into each position of p, from the first to the last -- p in turn is a list of lists, obtained by a recursive call to perm which excludes the first item of l (and thus permutes all other items in all possible ways).

If you don't understand recursion, it's not really trivial to explain;-). If you don't understand list comprehensions, they are trivial to explain -- that return is semantically equivalent to

result = []
for i in range(sz):
  for p in perm(l[1:]):
    result.append(p[:i]+[l[0]]+p[i:])
return result

this also shows how inefficient this code is: it's calling perm recursively sz times, and obviously there's no need for it. Much better would be to simply swap the two for loops:

result = []
for p in perm(l[1:]):
  for i in range(sz):
    result.append(p[:i]+[l[0]]+p[i:])
return result

and the equivalent of this, much better code, is a list comprehension with the two for clauses swapped:

return [p[:i]+[l[0]]+p[i:] for p in perm(l[1:]) for i in range(sz)]

Answer 4

Look at this:

>>> l = [1, 2, 3, 4, 5, 6]
>>> p = l[1:]
>>> p
[2, 3, 4, 5, 6]
>>> i = 3
>>> p[:i]
[2, 3, 4]
>>> p[i:]
[5, 6]
>>> p[:i]+[l[0]]+p[i:]
[2, 3, 4, 1, 5, 6]
>>> 

So, here's the thing, p stands for all permutations of l[1:] (ie, l minus the first element). Next, i is range(sz), which means it varies from 0 to the length of l. That will split p in two lists of all possible sizes (0 and sz, 1 and sz -1, 2 and sz - 2, etc), and insert the first element of l -- the one that didn't get permuted -- between these two lists.

Answer 5

The return statement is using a list comprehension. It's a bit easier to understand if you put it into actual loops:

value = []
for i in range(sz):
    # call this function using all but the first item in l
    for p in perm(l[1:]):
        # now place the first item in l between index i-1 and index i in p
        value.append(p[:i] + [l[0]] + p[i:])
return value