¿Cómo reescribir una función recursiva para usar un bucle en su lugar?

Este hilo de desbordamiento de stack afirma que cada función recursiva puede escribirse como un bucle.

¿Qué funciones recursivas no pueden reescribirse usando bucles?

Tiene sentido completo Pero no estoy seguro de cómo express la siguiente función recursiva como un bucle porque tiene una pieza de lógica pre-recursiva y una pieza de lógica post-recursiva.

Obviamente, la solución no puede utilizar la instrucción goto. El código está aquí:

def gen_perms(lst, k, m): if k == m: all_perms.append(list(lst)) else: for i in xrange(k, m+1): #swap char tmp = lst[k] lst[k] = lst[i] lst[i] = tmp gen_perms(lst, k+1, m) #swap char tmp = lst[k] lst[k] = lst[i] lst[i] = tmp 

Invocarlo sería así:

 all_perms = [] gen_perm([1, 2, 3], 0, 2) 

y genera cada permutación de la lista 1,2,3.

No estoy muy familiarizado con la syntax de python, pero el siguiente código (en ‘c’) no debería ser demasiado difícil de traducir, asumiendo que python puede hacer nesteds para las declaraciones.

 int list[3]={1,2,3}; int i,j,k; for(i=0;i < SIZE;i++) for(j=0;j < SIZE;j++) for(k=0;k < SIZE;k++) if(i!=j && j!=k && i!=k) printf("%d%d%d\n",list[i],list[j],list[k]); 

La forma más python de hacer permutaciones es usar:

 >>> from itertools import permutations >>> permutations([1,2,3]) >>> list(permutations([1,2,3])) [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)] 

Digamos que quieres encontrar todas las permutaciones de [1, 2, 3, 4]. Hay 24 (= 4!) De estos, así que numérelos 0-23. Lo que queremos es una forma no recursiva de encontrar la permuta Nth.

Digamos que ordenamos las permutaciones en orden numérico creciente. Entonces:

  • Permutaciones 0-5 comienzan con 1
  • Permutaciones 6-11 comienzan con 2
  • Permutaciones 12-17 comienzo con 3
  • Permutaciones 18-23 comienzan con 4

Así que podemos obtener el primer número de permutación N dividiendo N por 6 (= 3!), Y redondeando hacia arriba.

¿Cómo obtenemos el siguiente número? Mira los segundos números en permutaciones 0-5:

  • Las permutaciones 0-1 tienen segundo número 2.
  • Permutaciones 2-3 tienen segundo número 3.
  • Permutaciones 4-5 tienen segundo número 4.

Vemos una cosa similar con permutaciones 6-11:

  • Permutaciones 6-7 tienen segundo número 1.
  • Las permutaciones 8-9 tienen el segundo número 3.
  • Las permutaciones 10-11 tienen segundo número 4.

En general, tome el rest después de dividir por 6 antes, divídalo por 2 (= 2!) Y redondee hacia arriba. Eso le da 1, 2 o 3, y el segundo elemento es el primero, segundo o tercer elemento que queda en la lista (después de haber eliminado el primer elemento).

Puedes seguir así. Aquí hay un código que hace esto:

 from math import factorial def gen_perms(lst): all_perms = [] # Find the number of permutations. num_perms = factorial(len(lst)) for i in range(num_perms): # Generate the ith permutation. perm = [] remainder = i # Clone the list so we can remove items from it as we # add them to our permutation. items = lst[:] # Pick out each item in turn. for j in range(len(lst) - 1): # Divide the remainder at the previous step by the # next factorial down, to get the item number. divisor = factorial(len(lst) - j - 1) item_num = remainder / divisor # Add the item to the permutation, and remove it # from the list of available items. perm.append(items[item_num]) items.remove(items[item_num]) # Take the remainder for the next step. remainder = remainder % divisor # Only one item left - add it to the permutation. perm.append(items[0]) # Add the permutation to the list. all_perms.append(perm) return all_perms