给定一个范围列表，找到这些范围的所有组合，其总和为k

Question

我有34个数字范围。例如：

x1 = {25,35}
x2 = {28,36}
x3 = {15,20}
.
.
x34 = {28,37}

我必须找到所有的组合，这样我就可以从每个范围中选择一个数字，所有这34个数字加起来就是k。

例如：

let k = 600
so from x1 - we pick 26
from x2 - we pick 29
.
.
and from x34 we pick 16.
Then, x1 + x2 + x3 + x4 + … + x34 = 600.

我想要所有这样的组合。

用某种算法可行吗？

我想在python中实现这一点。

Answer 1

range(a, b)包括a，不包括b。所以这里的真实范围是：

{20, 25}
{30, 36}
{10, 39}

all_ranges = [range(20, 26), range(30, 37), range(10, 40)]
def get_combinations(ranges, k):
if ranges.__len__() == 0:
return int(k == 0)
combinations = 0
for i in ranges[0]:
#        if k - i < 0:
#            break
combinations += get_combinations(ranges[1:], k - i)
return combinations
print(get_combinations(all_ranges, 70))

我们将从k中减去直到零，而不是将数字相加直到它们达到k。

if ranges.__len__() == 0:
return int(k == 0)

这是终止递归的块。基本上，如果我们从k中减去从范围中选取的每个数字，那么结果必须为零。

combinations = 0
for i in ranges[0]:
combinations += get_combinations(ranges[1:], k - i)

请注意，注释的部分仅用于提高效率。所以我们在这里选择一个数字，我们最初选择它为k。然后，我们循环第一个范围的所有值，得到新的k - i和新的范围ranges[1:]的组合。你可以看到这些东西是如何结合在一起的。

编辑并更正答案

对不起，我没有注意到OP需要组合本身。尽管如此，我还是把上面的代码留给了未来的访问者。

使用与上面相同的逻辑，我们可以获得二维列表中的所有组合。

from copy import deepcopy
all_ranges = [range(20, 26), range(30, 37), range(10, 40)]
def get_combinations(ranges, k, initial_combination=None):
if not initial_combination:
initial_combination = []
combinations = []
if ranges.__len__() == 1:
for i in ranges[0]:
if k - i < 0:
return combinations
elif k - i == 0:
_ = deepcopy(initial_combination)
_.append(i)
combinations.append(_)
return combinations
for i in ranges[0]:
_ = deepcopy(initial_combination)
_.append(i)
combinations += get_combinations(ranges[1:], k - i, _)
return combinations
get_combinations(all_ranges, 70)

注意：深度复制功能

计算效率HACK

from copy import deepcopy
all_ranges = [range(10, 40), range(20, 30), range(40, 50)]

def get_minimums():
m = []
for index, r in enumerate(all_ranges):
m.append(sum([_.start for _ in all_ranges[index + 1:]]))
minimums = get_minimums() #[60, 40, 0]

def get_combinations(ranges, k, initial_combination=None):
if not initial_combination:
initial_combination = []
combinations = []
if ranges.__len__() == 1:
for i in ranges[0]:
if k - i < 0:
break
elif k - i == 0:
_ = deepcopy(initial_combination)
_.append(i)
print(_)
combinations.append(_)
return combinations
minimum = minimums[-ranges.__len__()]
for i in range(ranges[0].start, ranges[0].stop):
if k - minimum - i < 0:
break
_ = deepcopy(initial_combination)
_.append(i)
combinations += get_combinations(ranges[1:], k - i, _)
return combinations
get_combinations(all_ranges, 90)

Answer 2

您可以使用itertools的乘积方法来检查n个数组之间的所有组合。

例如：

import itertools
a = [1,2]
b = ['a' , 'b']
c = list(itertools.product(a,b))
>> [(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')]

因此，如果你想知道组成给定数字的所有组合，你只需要在最终列表中迭代并检查所有结果。

import itertools
x1 = range(25,35)
x2 = range(28,36)
x3 = range(15,20)
result = []
for item in list(itertools.product(x1,x2,x3)):
if sum(item) == 75:
result.append(item)
print(result)
>> [(25, 31, 19), (25, 32, 18), (25, 33, 17), (25, 34, 16), .....]

如果您以前不知道范围的数量，只需在itertools.product中使用*运算符，代码将是相同的

ranges = [range(1,5), range(5,29), range(3, 400), ...]
#STUFF
itertools.product(*ranges)