如何在指定的范围内找到与另一个数字相加的数字列表？

Question

使用Python

以下是一些要求：

我想找一张数字清单，上面写着：

1. 加起来等于一个数字(比方说30)
2. 在(开始，结束)范围内，比方说(8，20)
3. 在列表中有Y(例如3)元素

例: 8,10,12

我已经尝试了下面的代码，它适用于我想要的东西，但是它给了我内存非常重的所有组合。为了选择一个，我刚刚随机地选择了一个，但是我想用它来处理范围更大的列表，所以这是没有效率的。

list(combinations(list(range(8,20)),3))

Answer 1

您发布的代码不检查金额。

下面的片段优化了内存使用，而不是运行时

如果您使用的是Python3，那么combinations已经返回一个生成器。您所要做的就是对这些组合进行迭代。如果和是正确的，则从循环中打印组合和break：

from itertools import combinations

for comb in combinations(range(8, 20), 3):
    if sum(comb) == 30:
        print(comb)
        break

输出

(8, 9, 13)

或者，您可以使用filter，然后对结果调用next。通过这种方式，您可以获得任意数量的组合：

from itertools import combinations

valid_combs = filter(lambda c: sum(c) == 30, combinations(range(8, 20), 3))

print(next(valid_combs))
print(next(valid_combs))
print(next(valid_combs))

输出

(8, 9, 13)
(8, 10, 12)
(9, 10, 11)

更高级和更动态的解决方案是使用函数和yield from (如果您使用的是PythonJava3.3)：

from itertools import combinations


def get_combs(r, n, s):
    yield from filter(lambda c: sum(c) == s, combinations(r, n))


valid_combs = get_combs(range(8, 20), 3, 30)

print(next(valid_combs))
print(next(valid_combs))
print(next(valid_combs))

输出

(8, 9, 13)
(8, 10, 12)
(9, 10, 11)

Answer 2

下面是一个递归函数的例子，它将有效地完成这个任务。

def rangeToSum(start,stop,target,count):
    if count == 0: return []
    minSum = sum(range(start,start+count-1))
    stop   = min(stop,target+1-minSum)
    if count == 1 :
        return [target] if target in range(start,stop) else [] 
    for n in reversed(range(start,stop)):
        subSum = rangeToSum(start,n,target-n,count-1)
        if subSum: return subSum+[n]
    return []

print(rangeToSum(8,20,30,3)) # [8,10,12]

它的工作方式是先尝试最大的数字，然后调用自己在剩余的范围内找到与剩余值相加的数字。这将跳过无法产生目标和的整个组合。例如，尝试20次跳过包含19、18、16、15、14、13、12或11的组合。

它还考虑到第一个计数-1项将产生的最小和，以进一步减少停止值。例如，对于前两个数字，从8到30将使用至少17 (8+9)，因此范围的停止值可以减少到14，因为17 + 13将达到30，而任何更高的值都将超过30。

对于大量的数据，函数在大多数情况下会很快找到解决方案，但根据参数的组合也可能会花费很长的时间。

 rangeToSum(80000,20000000,3000000,10) # 0.6 second

 # [80000, 80002, 80004, 80006, 80008, 80010, 80012, 80014, 80016, 2279928]

如果您需要它更快，您可以尝试回忆录(例如使用函式工具lru_cache )。