<p><code>range(a, b)</code>包括a,不包括b。
因此这里的<em>实际范围</em>是:</p>
<pre><code>{20, 25}
{30, 36}
{10, 39}
</code></pre>
<pre><code>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))
</code></pre>
<p>我们将从<code>k</code>中减去数字,直到达到零,而不是将数字相加到<code>k</code></p>
<pre><code>if ranges.__len__() == 0:
return int(k == 0)
</code></pre>
<p>这是终止递归的块。基本上,如果我们从<code>k</code>的范围中减去每个数字,那么结果必须是零</p>
<pre><code>combinations = 0
for i in ranges[0]:
combinations += get_combinations(ranges[1:], k - i)
</code></pre>
<p>请注意,注释的部分仅用于效率。
所以我们在这里选择一个数字,我们最初选择它为<code>k</code>。然后,我们循环第一个范围的所有值,并获得新范围<code>k - i</code>与新范围<code>ranges[1:]</code>的组合。你可以看到这些东西是如何结合在一起的</p>
<h2>编辑并更正答案</h2>
<p>对不起,我没注意到OP需要这些组合。尽管如此,我还是将上述代码留给了未来的访问者</p>
<p>使用与上面相同的逻辑,我们可以得到二维列表中的所有组合</p>
<pre><code>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)
</code></pre>
<p>注:<a href="https://www.geeksforgeeks.org/copy-python-deep-copy-shallow-copy/#:~:text=In%20case%20of%20deep%20copy,using%20%E2%80%9Cdeepcopy()%E2%80%9D%20function." rel="nofollow noreferrer">deepcopy functionality</a></p>
<h2>计算效率黑客</h2>
<pre><code>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)
</code></pre>