Python - retrocedendo

O retrocesso é uma forma de recursão. Mas envolve escolher apenas uma opção entre todas as possibilidades. Começamos por escolher uma opção e retrocedemos a partir dela, se chegarmos a um estado em que concluamos que esta opção específica não dá a solução necessária. Repetimos essas etapas percorrendo cada opção disponível até obter a solução desejada.

Abaixo está um exemplo de como encontrar todas as ordens possíveis de arranjos de um determinado conjunto de letras. Quando escolhemos um par, aplicamos backtracking para verificar se aquele par exato já foi criado ou não. Se ainda não tiver sido criado, o par será adicionado à lista de respostas, caso contrário, será ignorado.

def permute(list, s):
    if list == 1:
        return s
    else:
        return [ y + x
                 for y in permute(1, s)
                 for x in permute(list - 1, s)
                 ]

print(permute(1, ["a","b","c"]))
print(permute(2, ["a","b","c"]))

Quando o código acima é executado, ele produz o seguinte resultado -

['a', 'b', 'c']
['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']