嵌套循环的替代方法

Mismaah

以这个代码为例

#Find all combinations of five positive integers whose reciprocals sum to 1 under a limit
limit = 30
none = True
reciprocals5 = []
for x in range(1,limit):
    for y in range(1,limit):
        for z in range(1,limit):
            for a in range(1,limit):
                for b in range(1,limit):
                    if(x!=y and x!=z and x!=a and x!=b and y!=z and y!=a and y!=a and y!=b and z!=a and z!=b and a!=b):
                        if(1/x + 1/y + 1/z + 1/a + 1/b == 1):
                            reciprocals5.append([x,y,z,a,b])
                            none = False

如果必须找到所有6个正整数组合，则必须添加另一个循环，依此类推。可以说我想找到所有N个正整数组合。由于我无法创建N个嵌套的for循环，替代方法是什么？

文件火

由于我无法创建N个嵌套的for循环，替代方法是什么？

递归！

有一个函数带有额外的参数，例如求和项的数目和目标数目，然后在其实现中以更少的项再次调用自身。

您的停止条件是合计项的数量为零。在这种情况下，如果要达到的目标数为零，则意味着您找到了有效的总和。如果非零，则表示您没有。（类似地，您可以在剩下的第一学期进行最后一次检查，检查是否可以选择一个匹配的最终数字。）

由于您只需要查找合计为1的不同数字集，因此可以假设x> y> z> a> b（或相反的顺序），以确保不会一次又一次地找到相同的序列，只是顺序不同。

同样，从极限向下迭代意味着倒数将随着您进行迭代而增加。这也意味着一旦总和超过1（或目标变为负数），您就可以停止寻找，这应该可以帮助您快速修剪不会产生新值的循环。

最后，Python还支持分数，这意味着您可以精确地进行这些计算，而不必担心浮点数的舍入问题。

放在一起：

from fractions import Fraction

def reciprocal_sums(n=5, limit=30, target=1, partial=()):
    if n == 0:
        if target == 0:
            yield partial
        return
    for i in range(limit, 0, -1):
        new_target = target - Fraction(1, i)
        if new_target < 0:
            return
        yield from reciprocal_sums(
            n - 1, i - 1, new_target, partial + (i,))

测试n = 5（默认值）：

>>> list(reciprocal_sums())
[(30, 20, 12, 3, 2),
 (30, 20, 6, 4, 2),
 (30, 10, 6, 5, 2),
 (28, 21, 12, 3, 2),
 (28, 21, 6, 4, 2),
 (28, 14, 7, 4, 2),
 (24, 12, 8, 4, 2),
 (20, 12, 6, 5, 2),
 (20, 6, 5, 4, 3),
 (18, 12, 9, 4, 2),
 (15, 12, 10, 4, 2)]

对于n = 4：

>>> list(reciprocal_sums(4))
[(24, 8, 3, 2),
 (20, 5, 4, 2),
 (18, 9, 3, 2),
 (15, 10, 3, 2),
 (12, 6, 4, 2)]

并且n = 6：

>>> list(reciprocal_sums(6))
[(30, 28, 21, 20, 3, 2),
 (30, 24, 20, 8, 4, 2),
 (30, 24, 10, 8, 5, 2),
 (30, 20, 18, 9, 4, 2),
 (30, 20, 15, 10, 4, 2),
 (30, 18, 10, 9, 5, 2),
 (30, 12, 10, 5, 4, 3),
 (28, 24, 21, 8, 4, 2),
 (28, 21, 20, 6, 5, 2),
 (28, 21, 18, 9, 4, 2),
 (28, 21, 15, 10, 4, 2),
 (28, 20, 14, 7, 5, 2),
 (28, 14, 12, 7, 6, 2),
 (28, 14, 7, 6, 4, 3),
 (24, 20, 12, 8, 5, 2),
 (24, 20, 8, 5, 4, 3),
 (24, 18, 9, 8, 6, 2),
 (24, 15, 10, 8, 6, 2),
 (24, 12, 8, 6, 4, 3),
 (20, 18, 12, 9, 5, 2),
 (20, 18, 9, 5, 4, 3),
 (20, 15, 12, 10, 5, 2),
 (20, 15, 10, 5, 4, 3),
 (18, 15, 10, 9, 6, 2),
 (18, 12, 9, 6, 4, 3),
 (15, 12, 10, 6, 4, 3)]

这个解决方案非常快。在Snapdragon 845 ARM CPU上运行：

%timeit list(reciprocal_sums(4)) 
365 ms ± 5.74 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit list(reciprocal_sums(5))
1.94 s ± 8.93 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit list(reciprocal_sums(6))
8.26 s ± 56.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

排序（降低每个级别的限制）以及在超过目标之后修剪最后一个级别将使此解决方案比评估所有可能排列或组合的解决方案快得多。

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。