Caçar com gato

O exercício 5.8 pede-nos que baralhemos uma cadeia de caracteres. Usámos o método shuffle do módulo random. Mas e se não soubermos da sua existência? Caçamos com gato ... Este não é um problema fácil. Existem várias soluções, umas mais elegantes e eficientes do que outras. Como ainda não se falou de recursividade vamos mesmo ter que caçar com um gato muito ... rafeiro: a iteração. Eis uma solução para o problema de gerar permutações de elementos guardados numa lista.

def permuta_it(lista):
    """
    Devolve as permutações de uma lista de elementos.
    """
    resultado = [[]]
    for i in range(len(lista)):
        aux_1 = []
        for elem in resultado:
            aux_2 =[]
            for j in range(len(elem) + 1):
                aux_2.append(elem[:j] + [lista[i]] + elem[j:])
            aux_1.extend(aux_2)
        resultado = aux_1[:]
    return resultado

Para chegarmos a esta solução baseámo-nos na ideia da construção indutiva da solução, método já referido em post anterior. A solução é construída etapa a etapa, de baixo para cima. Começando com uma lista vazia (linha 5), Entramos num ciclo (linhas 6 a 13), que será repetido tantas vezes quantos os elementos da nossa lista original. Dentro do ciclo, na primeira etapa, construímos todas as permutações de comprimento 1, com o primeiro elemento da lista original. Só há uma permutação! Depois, na etapa 2 do ciclo, pegamos nessa permutação e fabricamos todas as de comprimento 2, juntando o segundo elemento da lista original de todos os modos possíveis a cada uma das soluções da etapa anterior (linhas 7 a 12). Neste ficamos com as duas permutações de dois elementos. E assim sucessivamente, por cada etapa do ciclo, até termos usado todos os elementos da lista original. Vejamos dois exemplos:

>>> permuta_it([1,2,3])
[[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]
>>> permuta_it(['r','a','m','o'])
[['o', 'm', 'a', 'r'], ['m', 'o', 'a', 'r'], ['m', 'a', 'o', 'r'], ['m', 'a', 'r', 'o'], ['o', 'a', 'm', 'r'], ['a', 'o', 'm', 'r'], ['a', 'm', 'o', 'r'], ['a', 'm', 'r', 'o'], ['o', 'a', 'r', 'm'], ['a', 'o', 'r', 'm'], ['a', 'r', 'o', 'm'], ['a', 'r', 'm', 'o'], ['o', 'm', 'r', 'a'], ['m', 'o', 'r', 'a'], ['m', 'r', 'o', 'a'], ['m', 'r', 'a', 'o'], ['o', 'r', 'm', 'a'], ['r', 'o', 'm', 'a'], ['r', 'm', 'o', 'a'], ['r', 'm', 'a', 'o'], ['o', 'r', 'a', 'm'], ['r', 'o', 'a', 'm'], ['r', 'a', 'o', 'm'], ['r', 'a', 'm', 'o']]
>>>