递归生成 Python 中集合元素之间所有可能的计算

Question

我很难理解为什么以下递归代码（函数 count()）给出了错误的计算计数，但是基于手动编写的嵌套 for 循环（函数 count2()）给出了正确的计数，这是 n! * 4 ^ (n-1)?

（此时不用管输出变量。如果我能先解决这个难题，我稍后会用到它。）

我希望创建一个递归函数，它可以为任意长度的列表创建计算，这就是为什么简单地嵌套 for 循环不够好。

import itertools
import operator
# 
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. 
# 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

递归生成 Python 中集合元素之间所有可能的计算

Recursively generating all the possible calculations between set elements in Python

python

recursion

permutation