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.

view sourceprint?

01.def permuta_it(lista):

02.    """

03.    Devolve as permutações de uma lista de elementos.

04.    """

05.    resultado = [[]]

06.    for i in range(len(lista)):

07.        aux_1 = []

08.        for elem in resultado:

09.            aux_2 =[]

10.            for j in range(len(elem) + 1):

11.                aux_2.append(elem[:j] + [lista[i]] + elem[j:])

12.            aux_1.extend(aux_2)

13.        resultado = aux_1[:]

14.    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:

view sourceprint?

1.>>> permuta_it([1,2,3])

2.[[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]

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

4.[['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']]

5.>>>