Pythonのset要素間に可能なすべての計算を再帰的に生成する

Question

次の再帰的コード（関数count（））が誤った計算回数を与える理由を理解するのは困っていますが、 count2（））は、右のカウントを返します。 * 4 ^（n-1）？

（この時点では、出力変数を気にしない。私が最初にこのパズルを解くことができれば、私は、後でそれを使用します。）

私はリストのための計算を作成することができ再帰関数を作成したいです任意の長さです。なぜなら、単純にループの入れ子にするだけでは十分ではありません。

import itertools 
import operator 
# http://stackoverflow.com/questions/2983139/assign-operator-to-variable-in-python 
ops = { 
    0: operator.add, 
    1: operator.sub, 
    2: operator.mul, 
    3: operator.truediv 
} 
comb = [4, 1, 2, 3] 
perms = list() 
# itertools.permutations is not subscriptable, so this is a mandatory step. 
# See e.g. http://stackoverflow.com/questions/216972/in-python-what-does-it-mean-if-an-object-is-subscriptable-or-not 
# for details. 
for i in itertools.permutations(comb): 
    perms.append(i) 
output = list() 
output2 = list() 

# In theory, there are n! * 4^(n-1) possibilities for each set. 
# In practice however some of these are redundant, because multiplication and 
# addition are indifferent to calculation order. That's not tested here; 
# nor is the possibility of division by zero. 

# Variable debug is there just to enable checking the calculation count; 
# it serves no other purpose. 
debug = list() 
debug2 = list() 

def count(i): 
    for j in range(len(i)): 
     for op in ops: 
      if j+1 < len(i): 
       res = ops[op](i[j], i[j+1]) 
       if j+2 < len(i): 
        ls = list(i[j+1:]) 
        ls[0] = res 
        count(ls) 
       else: 
        debug.append([len(i), i[j], ops[op], i[j+1], res]) 
        if res == 10: output.append(res) 

def count2(i): 
    for j in range(len(i)): 
     for op in ops: 
      if j+1 < len(i): 
       res = ops[op](i[j], i[j+1]) 
       for op2 in ops: 
        if j+2 < len(i): 
         res2 = ops[op2](res, i[j+2]) 
         for op3 in ops: 
          if j+3 < len(i): 
           res3 = ops[op3](res2, i[j+3]) 
           debug2.append(res3) 
           if res3 == 10: output2.append(res3) 

for i in perms: 
    count(i) 
    count2(i) 
print(len(debug)) # The result is 2400, which is wrong. 
print(len(debug2)) # The result is 1536, which is correct. 

Answer 1

再帰関数にあまりに多くの再利用関数を追加しています。あなたの例を詳しく説明しましょう。元の順列を数えることを考えてみましょう。コール

count([4, 1, 2, 3]) 

は、次の再帰呼び出しを生じるはずである：

count([5, 2, 3]) # + 
count([3, 2, 3]) # - 
count([4, 2, 3]) # * 
count([4, 2, 3]) #/

そして、それは右、任意の結果を追加してはいけません！

count([3, 3]) # these calls are premature 
count([-1, 3]) # since they reduce 1, 2 
count([2, 3]) # and do not consider 
count([0.5, 3]) # the first element 4 

と早すぎる平等にあるすべての[2, 3]計算の結果を追加：あなたはトップレベルのコールでインデックスをループしているので、しかし、それは、さらに以下の再帰呼び出しのすべてにつながります！そして、あなたが本当にあなたの再帰関数で何をしたいのか

、要素のみのを最初のペアを削減することである（ない隣接する要素のすべてのペア！）と再帰的に結果のリストの計算を数えます。したがって、あなたの機能は次のように単純化することができます：

def count(lst): 
    # no mo' looping through the list. That's why we do recursion! 
    for op in ops.values(): 
     if len(lst) > 1: 
      res = op(*lst[:2]) # reduce first pair 
      if len(lst) > 2: 
       ls_short = [res] + list(lst[2:]) 
       count(ls_short) 
      else: 
       debug.append(res) 

... 
> print(len(debug)) 
1536