Cómo entender el algoritmo de generación de todas las posibles secuencias de símbolos utilizando una función generadora y recursión.
Intento entender el algoritmo de la función a continuación y nada me ayuda a entender este algoritmo, incluso la depuración profunda utilizando este enlace https://pythontutor.com/visualize.html. Debo señalar que entiendo los iteradores y generadores con seguridad, pero esto me ha confundido.
Por favor, explícame cómo funciona.
El código:
def permute(seq):
"""
Esta función devuelve todas las posibles combinaciones únicas de símbolos en una secuencia
Ejemplo con la cadena "xyz":
xyz, xzy, zxy, zyx, yxz, yzx
:param seq: cualquier secuencia
"""
if not seq:
yield seq
else:
for i in range(len(seq)):
rest = seq[:i] + seq[i + 1:]
for x in permute(rest):
yield seq[i:i + 1] + x
string1 = "hard"
print(*(permute(string1))) # hard hadr hrad hrda hdar hdra ahrd ahdr arhd ardh adhr adrh rhad rhda rahd radh rdha rdah dhar dhra dahr darh drha drah
davy.ai
La función
permutees un generador recursivo que toma una secuencia,seq, como entrada y genera todas las posibles permutaciones únicas de la secuencia.Si la secuencia de entrada está vacía, la función devuelve una secuencia vacía. De lo contrario, toma cada elemento de la secuencia de entrada,
seq[i:i+1], y lo agrega a una permutación de los elementos restantes,x, generada mediante una llamada recursiva apermuteen los elementos restantes de la secuencia de entrada,rest. La llamada recursiva genera todas las permutaciones únicas derest, y el bucleforitera a través de cada una de estas permutaciones y agrega el elemento actual para crear una nueva permutación.La función continúa llamándose a sí misma recursivamente en secuencias cada vez más cortas hasta que solo queda un elemento, momento en el que genera una permutación que consiste en ese último elemento.
Cuando las llamadas recursivas han terminado de generar todas las posibles permutaciones, las declaraciones
yielden cada llamada devuelven la permutación actual al siguiente nivel en la pila de llamadas. La declaraciónyieldmás externa de la llamada inicial apermuteluego devuelve la secuencia final de permutaciones.El ejemplo proporcionado en el código muestra cómo la función genera todas las posibles permutaciones de la secuencia de entrada “hard”, incluyendo “hard”, “hadr”, “hrad”, “hrda”, “hdar”, “hdra”, “ahrd”, “ahdr”, “arhd”, “ardh”, “adhr”, “adrh”, “rhad”, “rhda”, “rahd”, “radh”, “rdha” y “drah”.