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

The program defines a python function that returns the list of permutations. The program checks if the length of the input list is less than or equal to one. The function declaration identifies the input and output as lists.

The for loop iterate through the list and the permutations are saved in an empty list in the next loop statement. At the end of the program, the list of lists is returned.