Python - Retroceso

El retroceso es una forma de recursividad. Pero implica elegir la única opción entre todas las posibilidades. Comenzamos eligiendo una opción y retrocedemos de ella, si llegamos a un estado en el que concluimos que esta opción específica no da la solución requerida. Repetimos estos pasos recorriendo cada opción disponible hasta que obtengamos la solución deseada.

A continuación se muestra un ejemplo de cómo encontrar todo el orden posible de arreglos de un conjunto de letras dado. Cuando elegimos un par, aplicamos retroceso para verificar si ese par exacto ya se ha creado o no. Si aún no se ha creado, el par se agrega a la lista de respuestas; de lo contrario, se ignora.

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"]))

Cuando se ejecuta el código anterior, produce el siguiente resultado:

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