使用多个列表查找总和为N的所有组合

Given:

鉴于：

m number of lists (m can vary).
m个列表（m可以变化）。
Each list contain arange() of numbers.
每个列表都包含一个数字范围（）。

Want:

想：

Find the m-tuple (one number per list) that sum() to N.
找到sum（）到N的m-tuple（每个列表一个数字）。

What I have:

我拥有的：

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.

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

3 个解决方案

#1

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

正如评论中所讨论的，范围都是相同的，我们应该使用整数。这是一个非常好的方式。

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:

而不是生成四个数字并测试它们是否加起来为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.这里是代码：

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)

That prints:

打印：

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

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

它非常高效，因为它可以非常直接地生成组合。 if max（combi）仅过滤掉[0,0,0,10]，[0,0,10,0]，[0,10,0,0]和[10,0,0,0]>

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

这是你的原版，我的和@Mijamo之间的速度比较，有100个数字，如你的例子：

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

Full code for that test:

该测试的完整代码：

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

#2

All the combinations can be retrieved this way:

可以通过以下方式检索所有组合：

combinations = itertools.product(np.arange(0,1,0.01), repeat = m)

https://docs.python.org/3.5/library/itertools.html#itertools.product

And as it is a generator, you can then make a new generator to return the tupples that sum to n this way

因为它是一个生成器，你可以创建一个新的生成器，以这种方式返回总和为n的tupples

results = (tuple for tuple in combinations if sum(tuple) == N)

#3

how about using "product" from itertools to get all possible m-length tuples. Then you just filter by the condition that the tuple sum == N

如何使用itertools中的“product”获取所有可能的m-length元组。然后你只需要通过元组和= = N的条件进行过滤

#1