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?
