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:])]
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
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.
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)]
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:
http://stackoverflow.com/questions/2565619/algorithm-for-python-itertools-permutations
http://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list-in-python
Okay, let's begin.
(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:])]
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:])]
l to ssz, instead using len(s) directly. We might lose a tiny bit of efficiency, but we gain a huge amount of readabilitydef 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
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
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.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
perm function call. Now, the shortperms variable will contain all the permutations of s[1:], which is s minus the first item.shortpermpermutationsdef 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.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