CODEWITHSUNDEEP
python
joefromct
joefromct

Reputation: 1556

find all elements in a list of positive numbers that add up to number X

I'm trying to reverse engineer a legacy report and using python to solve the problem.

The legacy report has an end sum number of 200,000.

I know a collection of the numbers that could end up to this 200k, but this collection is littered with many other numbers that are to be filtered out (with logic i'm yet to understand).

In python, How could i iterate through the list of numbers to find all entries (sub-lists) of variable length (could be 1 element that = 200k, or the product of 15 elements...) that would add up to the 200k?

I started to write it out, then decided to ask for help when i realized element #1 + 2 could overflow but list element #1 + 4 + 7 could be a match to the 200k....

It's almost like factorization, however with the sum's instead of the products, and within a list of possible candidates.

Not sure. Any ideas? Anyone ever done anything like this?

Additional Details:
With permutations and numpy i'm getting a result as expected, however it is taking far too long with the expected inputs and outputs. (i.e. days..?)

below is where I am at:

Below seems to give correct results, although it seems it will take awhile.

I'll accept the answer above and let this run over night.

Thanks, 

from itertools import permutations 
import numpy , pickle, random
output_results = {} 
input_array = [random.randrange(0,15000) for i in range(1000)]
desired_sum = 200000
#input_array = (1,2,9,13,12) 
#desired_sum = 23 

for r in range(1,len(input_array)): 
    for p in permutations(input_array, r):
        temp_sum = numpy.sum(p) 
        if temp_sum == desired_sum: 
            output_results[p] = numpy.sum(p) 
    if r % 10 == 0:
        print "Finished up to number %s " % r 

pickle.dump( output_results, open( "save.p", "wb" ) )

Upvotes: 0

Views: 493

Answers (1)

Francesco Montesano
Francesco Montesano

Reputation: 8668

Itertools.permutations can help.

Varying the value of r in permutations(iterable, r) you can try to find all the possible permutations containing r entries from iterable (your collection), of which you can easily get sums (e.g. with numpy.sum).

If you have some idea of what to expect and set a reasonable upper limit for r you should get an answer in a reasonable time

edit

@joefromct: you can first estimate the largest value of r needed to find the solution you want in the following way (is not tested, but the idea should be correct)

sorted_input = np.sorted(input_array)
cumsum = np.cumsum(sorted_input)
max_r = (cumsum<desired_sum).sum()
if max_r == len(input_array) and sorted_input[-1] < desired_sum:
    print("sorry I can't do anything for you")
    exit()

for r in range(1,max_r):
    [...]

Upvotes: 1

Related Questions