この関数から再帰を削除することはできますか？

Question

私はこれでしばらく遊んでいますが、明らかな解決策が見当たりません。 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)

この関数は、X個のビー玉をYスロットに入れる方法の数を計算しています。出力例を次に示します。

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

@Joel Coehoorn'sの素朴な実装提案は次のとおりです。

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

例：

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

itertools.product

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

ネストされたループに基づく

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) 

例：

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

再帰と考えるものはすべて、スタックベースの問題と考えることもできます。この場合、再帰関数は、別個のスタックを作成するのではなく、プログラムの呼び出しスタックを使用します。つまり、代わりにスタックを使用して再帰関数を書き換えることができます。

私はあなたに実装を与えるのに十分なPythonを知らないが、それは正しい方向にあなたを向けるはずです。しかし、一言で言えば、関数の初期引数をスタックにプッシュし、スタックのサイズがゼロより大きい限り実行されるループを追加します。ループの繰り返しごとに1回ポップし、関数が現在それ自体を呼び出すたびにプッシュします。

Answer 3

すべての順列を作成するためにこのコードを見てください。問題に似たものを実装するのは比較的簡単だと思います。

リストのすべての順列を生成する方法python？