¿Es posible eliminar la recursión de esta función?

He estado jugando con esto por un tiempo, y simplemente no puedo ver una solución obvia. Quiero eliminar la recursión de la función XinY_Go.

def XinY_Go(x,y,index,slots): if (y - index) == 1: slots[index] = x print slots slots[index] = 0 return for i in range(x+1): slots[index] = xi XinY_Go(x-(xi), y, index + 1, slots) def XinY(x,y): return XinY_Go(x,y,0,[0] * y) 

La función es calcular el número de formas de colocar X canicas en las ranuras Y. Aquí hay algunos resultados de muestra:

  >>> xy.XinY (1,2)
  [1, 0]
  [0, 1]
  >>> xy.XinY (2,3)
  [2, 0, 0]
  [1, 1, 0]
  [1, 0, 1]
  [0, 2, 0]
  [0, 1, 1]
  [0, 0, 2]

Una implementación ingenua de la sugerencia de @Joel Coehoorn sigue:

 def XinY_Stack(x, y): stack = [(x, 0, [0]*y)] while stack: x, index, slots = stack.pop() if (y - index) == 1: slots[index] = x print slots slots[index] = 0 else: for i in range(x + 1): slots[index] = xi stack.append((i, index + 1, slots[:])) 

Ejemplo:

 >>> XinY_Stack(2, 3) [0, 0, 2] [0, 1, 1] [0, 2, 0] [1, 0, 1] [1, 1, 0] [2, 0, 0] 

Basado en itertools.product

 def XinY_Product(nmarbles, nslots): return (slots for slots in product(xrange(nmarbles + 1), repeat=nslots) if sum(slots) == nmarbles) 

Basado en bucles nesteds

 def XinY_Iter(nmarbles, nslots): assert 0 < nslots < 22 # 22 -> too many statically nested blocks if nslots == 1: return iter([nmarbles]) # generate code for iter solution TAB = " " loopvars = [] stmt = ["def f(n):\n"] for i in range(nslots - 1): var = "m%d" % i stmt += [TAB * (i + 1), "for %s in xrange(n - (%s)):\n" % (var, '+'.join(loopvars) or 0)] loopvars.append(var) stmt += [TAB * (i + 2), "yield ", ','.join(loopvars), ', n - 1 - (', '+'.join(loopvars), ')\n'] print ''.join(stmt) # exec the code within empty namespace ns = {} exec(''.join(stmt), ns, ns) return ns['f'](nmarbles + 1) 

Ejemplo:

 >>> list(XinY_Product(2, 3)) [(0, 0, 2), (0, 1, 1), (0, 2, 0), (1, 0, 1), (1, 1, 0), (2, 0, 0)] >>> list(XinY_Iter(2, 3)) def f(n): for m0 in xrange(n - (0)): for m1 in xrange(n - (m0)): yield m0,m1, n - 1 - (m0+m1) [(0, 0, 2), (0, 1, 1), (0, 2, 0), (1, 0, 1), (1, 1, 0), (2, 0, 0)] 

Todo lo que pensamos como recursión también puede considerarse como un problema basado en la stack, donde la función recursiva solo usa la stack de llamadas del progtwig en lugar de crear una stack separada. Eso significa que cualquier función recursiva puede reescribirse usando una stack en su lugar.

No conozco a Python lo suficientemente bien como para darte una implementación, pero eso debería orientarte en la dirección correcta. Pero en pocas palabras, presione los argumentos iniciales para la función en la stack y agregue un bucle que se ejecute siempre que el tamaño de la stack sea mayor que cero. Pop una vez por iteración de bucle, presione cada vez que la función se llame a sí misma.

Mire este código para crear todas las permutaciones, creo que sería relativamente sencillo implementar algo similar para su problema.

¿Cómo generar todas las permutaciones de una lista en python?