All geek questions in one place

Python newbie gets confused by a complex line of code

I understand the essence of the code that it generates permutations; however, I was wondering if anyone could explain what happens in the return.

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:])]
+4
source share
5 answers

This return returns an understanding of the list, the elements of which are created by inserting the first element l at each position p , from the first to the last - p , in turn, is a list of lists obtained by the recursive call to perm , which excludes the first element l (and thus , rearranges all other elements in all possible ways).

If you do not understand recursion, this is not entirely trivial to explain ;-). If you do not understand the understanding of lists, they trivial to explain - that return semantically equivalent

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

it also shows how inefficient this code is: it calls perm recursively sz times, and obviously there is no need for it. It would be much better to just 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 understanding the list with replacing two for :

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

The return statement uses list comprehension. This is a little easier to understand if you put it in 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
+5
source

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 the thing p denotes all permutations l[1:] (ie l minus the first element). Then i is range(sz) , which means it changes from 0 to length l . This will split p into two lists of all possible sizes (0 and sz, 1 and sz -1, 2 and sz - 2, etc.) and insert the first element l - the one that did not receive the permutation - between the two lists.

+2
source

Ok, let's get started.

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

Version 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 may lose a small part of the efficiency, but we get a lot of readability.
  • Correct interval in list comprehension

Version 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
  • Share your list comprehension.

Version 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 for loops. Now you can say: for each permutation, take each position i and add a copy of this permutation with s[0] inserted at each position i . This will become clearer in the next few versions.

Version 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 perm function perm . Now the shortperms variable will contain all permutations s[1:] , which is s minus the first element.
  • Added adding a list to three operations:
    • Make a copy of shortperm
    • Insert the first element in s
    • Add this list to permutations

Version 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) same as len(shortperm) + 1 , because each shortperm is a permutation of elements in s , minus the first. However, this is probably more readable.

Final code

With 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
+1
source

Source: https://habr.com/ru/post/1306073/

More articles:


All Articles