IN PYTHON 3 NOT 2 implement the function permutations that t

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]]

Solution

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: