用多个列表查找总和为N的所有组合 [英] Find all combination that sum to N with multiple lists

问题描述

给出:

• m列表数(m可能有所不同).
• 每个列表包含数字arange().

• m number of lists (m can vary).
• Each list contain arange() of numbers.

想要:

• 找到sum()至N的m元组(每个列表一个数字).

• Find the m-tuple (one number per list) that sum() to N.

我有什么:

• 我可以在固定数量的列表中找到所有组合.

• I can find all combination in a static number of lists.

import numpy as np
for a in np.arange(0,1,0.01):
    for b in np.arange(0,1,0.01):
        for c in np.arange(0,1,0.01):
            for d in np.arange(0,1,0.01):
                if (a+b+c+d) == 1.0: 
                    print a,b,c,d

我也想找到一种最佳的计算方法.

I would also like to find an optimal way to compute this as well.

推荐答案

如注释中所述，范围都是相同的，我们应该使用整数.这是一种完美的方法.

As discussed in the comments, the ranges are all the same and we ought to use integers. Here's an imho neat way then.

产生三个数字，而不是生成四个数字并测试它们是否相加为10，将定义间隔[0，10]分为四个间隔的三个数字.例如，当我们在(3，4，8)处切割时，我们将端点0和10相加，那么我们就有了边界(0，3，4，8，10).相邻边界之间的差异为(3-0、4-3、8-4、10-8)=(3、1、4、2).这是四个数字加起来等于10.这是执行此操作的代码:

Instead of producing four numbers and testing whether they add up to 10, produce three numbers defining a partition of the interval [0, 10] into four intervals. For example when we have the cuts at (3, 4, 8), and we add the end points 0 and 10, then we have the boundaries (0, 3, 4, 8, 10). The differences between adjacent boundaries are (3-0, 4-3, 8-4, 10-8) = (3, 1, 4, 2). That's four numbers adding up to 10. Here's code doing that:

n = 10
import itertools, operator
for cuts in itertools.combinations_with_replacement(range(n+1), 3):
    combi = list(map(operator.sub, cuts + (n,), (0,) + cuts))
    if max(combi) < n:
        print(combi)

打印:

[0, 0, 1, 9]
[0, 0, 2, 8]
[0, 0, 3, 7]
[0, 0, 4, 6]
[0, 0, 5, 5]
[0, 0, 6, 4]
[0, 0, 7, 3]
[0, 0, 8, 2]
[0, 0, 9, 1]
[0, 1, 0, 9]
[0, 1, 1, 8]
[0, 1, 2, 7]
...
...
[7, 2, 0, 1]
[7, 2, 1, 0]
[7, 3, 0, 0]
[8, 0, 0, 2]
[8, 0, 1, 1]
[8, 0, 2, 0]
[8, 1, 0, 1]
[8, 1, 1, 0]
[8, 2, 0, 0]
[9, 0, 0, 1]
[9, 0, 1, 0]
[9, 1, 0, 0]

这非常有效，因为它可以非常直接地产生组合. if max(combi) < n仅过滤掉[0, 0, 0, 10]，[0, 0, 10, 0]，[0, 10, 0, 0]和[10, 0, 0, 0].

It's very efficient, since it produces the combinations pretty directly. The if max(combi) < n only filters out [0, 0, 0, 10], [0, 0, 10, 0], [0, 10, 0, 0] and [10, 0, 0, 0].

以下是您的原始，我的和@Mijamo的速度比较，范围为100，例如您的示例:

Here's a speed comparison between your original, mine, and @Mijamo's, with a range of 100 numbers like in your example:

  drum: 21.027 seconds
Stefan:  0.708 seconds
Mijamo: 62.864 seconds

该测试的完整代码:

import itertools, operator
from timeit import timeit

def drum(n):
    out = []
    for a in range(n):
        for b in range(n):
            for c in range(n):
                for d in range(n):
                    if a + b + c + d == n:
                        out.append((a, b, c, d))
    return out

def Stefan(n):
    combinations = (map(operator.sub, cuts + (n,), (0,) + cuts)
                    for cuts in itertools.combinations_with_replacement(range(n+1), 3))
    return [c for c in combinations if max(c) < n]

def Mijamo(n):
    combinations = itertools.product(range(n), repeat=4)
    return [tuple for tuple in combinations if sum(tuple) == n]

for func in drum, Stefan, Mijamo:
    print '%6s: %6.3f seconds' % (func.__name__, timeit(lambda: func(100), number=1))

这篇关于用多个列表查找总和为N的所有组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！