range(a, b)
a included, b excluded.
So here the real ranges are:
{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))
Instead of adding numbers till they reach k
, we will subtract from k
till reaching zero.
if ranges.__len__() == 0:
return int(k == 0)
This is the block which terminates the recursive. Basically if we subtract each number picked from the ranges from k
, then the result must be zero.
combinations = 0
for i in ranges[0]:
combinations += get_combinations(ranges[1:], k - i)
Note that the parts commented are for efficiency only.
So we are picking a number here, we choose it initially to be k
. We then loop over all values of the first range, and get the combinations of the new k - i
with the new ranges ranges[1:]
. You can see how those things fit together.
Edit and correct answer
Pardon me, I didn't notice OP needed the combinations themselves. Nonetheless, I left the above code for future visitors.
Using the same logic as above, we can get all combinations in a 2 dimensional list.
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)
Note: deepcopy functionality
Computational Efficiency 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)