CODEWITHSUNDEEP
python
tiffany123
tiffany123

Reputation: 1

how to find one list of numbers within specified range that sum to another number?

Using Python

Here's some requirements:

I want to find a list of of numbers [ ] that:

  1. add up to a number (say 30)

  2. Be within a range of (start,end) let's say (8, 20)

  3. Have Y (say 3) elements within the list

Ex: [8,10,12]

I've tried the code below, which works for what I want, but it gives me ALL combinations which is very heavy on memory. To select one, I've just randomly selected one, however I would like to use this for bigger lists with greater ranges, so this is not efficient.

list(combinations(list(range(8,20)),3))

Upvotes: 0

Views: 87

Answers (2)

Alain T.
Alain T.

Reputation: 42133

Here's an example of a recursive function that will do this efficiently.

def rangeToSum(start,stop,target,count):
    if count == 0: return []
    minSum = sum(range(start,start+count-1))
    stop   = min(stop,target+1-minSum)
    if count == 1 :
        return [target] if target in range(start,stop) else [] 
    for n in reversed(range(start,stop)):
        subSum = rangeToSum(start,n,target-n,count-1)
        if subSum: return subSum+[n]
    return []

print(rangeToSum(8,20,30,3)) # [8,10,12]

The way it works is by trying the largest numbers first and calling itself to find numbers in the remaining range that add up to the remaining value. This will skip whole swats of combinations that cannot produce the target sum. e.g. trying 20 skips over combinations containing 19,18,16,15,14,13,12 or 11.

It also takes into account the minimum sum that the first count-1 items will produce to further reduce the stop value. e.g. to reach 30 from 8 with 3 numbers will use at least 17 (8+9) for the first two numbers so the stop value of the range can be reduced to 14 because 17 + 13 will reach 30 and any higher value will go beyond 30.

For large numbers, the function will find a solution quickly in most cases but it could also take a very long time depending on the combination of parameters.

 rangeToSum(80000,20000000,3000000,10) # 0.6 second

 # [80000, 80002, 80004, 80006, 80008, 80010, 80012, 80014, 80016, 2279928]

If you need it to be faster, you could try memoization (e.g. using lru_cache from functools).

Upvotes: 0

DeepSpace
DeepSpace

Reputation: 81594

The code you posted does not check for the sum.

The below snippets optimize memory use, not run time

If you are using Python 3 then combinations already returns a generator. All you have to do is iterate over the combinations. If the sum is correct, print the combination and break from the loop:

from itertools import combinations

for comb in combinations(range(8, 20), 3):
    if sum(comb) == 30:
        print(comb)
        break

Outputs

(8, 9, 13)

Alternatively, you could use filter and then call next on the result. This way you can get as many combinations as you want:

from itertools import combinations

valid_combs = filter(lambda c: sum(c) == 30, combinations(range(8, 20), 3))

print(next(valid_combs))
print(next(valid_combs))
print(next(valid_combs))

Outputs

(8, 9, 13)
(8, 10, 12)
(9, 10, 11)

A bit more advanced and dynamic solution is with a function and yield from (if you are using Python >= 3.3):

from itertools import combinations


def get_combs(r, n, s):
    yield from filter(lambda c: sum(c) == s, combinations(r, n))


valid_combs = get_combs(range(8, 20), 3, 30)

print(next(valid_combs))
print(next(valid_combs))
print(next(valid_combs))

Outputs

(8, 9, 13)
(8, 10, 12)
(9, 10, 11)

Upvotes: 1

Related Questions