Implementar uma função que gere permutações de uma lista (Não pode usar from itertools import permutations )

Implemente a função permutations() que aceita uma lista lst como entrada e retorna uma lista de todas as permutações de lst (de modo que o valor retornado seja uma lista de listas). Faça isso recursivamente da seguinte forma: se a lista de entrada lst tiver o tamanho 1 ou 0, basta retornar uma lista contendo a lista lst. Caso contrário, faça uma chamada recursiva na sublista 1[1:] para obter a lista de todas as permutações de todos os elementos de lst, exceto o primeiro elemento 1[0].

Depois, para cada permutação (ou seja, lista) perm, gere permutações de lst inserindo lst[0] em todas as posições possíveis de 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]]

Alguma ideia?

def permutations(lst): if not lst: return [[]] res = [] for e in lst: temp = lst[:] temp.remove(e) res.extend([[e] + r for r in permutations(temp)]) return res print(permutations([1, 2])) print(permutations([1, 2, 3])) print(permutations([1, 2, 3, 4]))