I have 34 ranges of numbers. For example :
x1 = {25,35}
x2 = {28,36}
x3 = {15,20}
.
.
x34 = {28,37}
I have to find all combinations such that i choose a number from every range and all those 34 numbers sums up to k.
For example :
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.
I want all such combinations.
Is it feasible with some algorithm?
I want to implement this in python.
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.
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
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)
You can use itertools' product method to check all combinations between n number of arrays.
For example:
import itertools
a = [1,2]
b = ['a' , 'b']
c = list(itertools.product(a,b))
>> [(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')]
So if you want to know all the combinations that make a given number, you only have to iterate in the final list and check all the results.
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), .....]
If you don't know previously know the number of ranges you simply use the * operator in the itertools.product and the code will be the same
ranges = [range(1,5), range(5,29), range(3, 400), ...]
#STUFF
itertools.product(*ranges)