IN PYTHON 3 (NOT 2) implement the function permutations() that takes a list lst
ID: 3928575 • Letter: I
Question
IN PYTHON 3 (NOT 2) implement the function permutations() that takes a list lst as input and returns a list of all permutations of lst (so the returned value is a list of lists). Do this recursively as follows: If the input list lst is of size 1 or 0, just return a list containing list lst. Otherwise, make a recursive call on the sublist l[1:] to obtain the list of all permutations of all elements of lst except the first element l[0]. Then, for each such permutation (i.e., list) perm, generate permutations of lst by inserting lst[0] into all possible positions of perm.
>>> permutations([1, 2])
[[1, 2], [2, 1]]
>>> permutations([1, 2, 3])
[[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3, 2, 1]]
>>> permutations([1, 2, 3, 4])
[[1, 2, 3, 4], [2, 1, 3, 4], [2, 3, 1, 4], [2, 3, 4, 1],
[1, 3, 2, 4], [3, 1, 2, 4], [3, 2, 1, 4], [3, 2, 4, 1],
[1, 3, 4, 2], [3, 1, 4, 2], [3, 4, 1, 2], [3, 4, 2, 1],
[1, 2, 4, 3], [2, 1, 4, 3], [2, 4, 1, 3], [2, 4, 3, 1],
[1, 4, 2, 3], [4, 1, 2, 3], [4, 2, 1, 3], [4, 2, 3, 1],
[1, 4, 3, 2], [4, 1, 3, 2], [4, 3, 1, 2], [4, 3, 2, 1]]
Explanation / Answer
Please find the required program along with its output. Please see the comments against each line to understand the step.
def addpermutation(x,l): #add the permutation x into the list l
return [ l[0:i] + [x] + l[i:] for i in range(len(l)+1) ]
def permutations(l):
if len(l) == 0: #if the list size is 0, then return the empty list
return [[]];
return [x for y in permutations(l[1:]) for x in addpermutation(l[0],y) ] #else recursively call the permutations for all lists with size - 1 (truncated list)
print (permutations([1,2,3,4]))
-----------------------------------------------
OUTPUT: