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

Question

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] = x-i
      XinY_Go(x-(x-i), y, index + 1, slots)

def XinY(x,y):
   return XinY_Go(x,y,0,[0] * y)

La función está calculando la cantidad de formas de colocar X canicas en las ranuras Y. Aquí hay un ejemplo de salida:

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

Answer 1

Una implementación ingenua de @Joel Coehoorn's La sugerencia 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] = x-i
                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 anidados

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

Answer 2

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

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

Answer 3

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

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