python - Given a list of ranges, find all combination for these ranges that sums upto k

Question

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.

Answer 1

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)