CODEWITHSUNDEEP
pythonalgorithmoptimization
triplebig
triplebig

Reputation: 432

Making list of all possible sums up to a certain value

I need to make an effective algorithm for getting all possible sums (EDIT: pairwise) of elements from one list (including themselves), and storing them into another list up to a certain value.

For instance, if the value is 30, and the list is [1,2,3,4,5,15,20], I want a list that is: 

[1,2,3,4,5,6,7,8,9,10,15,16,17,18,19,20,21,22,23,24,25,30]

Right now I have a algorithm that works, yet is extremely ineffective (I need to do this up to 29000:

sumlist = [0]*60000
for j in range(0,len(abundlist)):
  for i in range(j,len(abundlist)):
    if sumlist[abundlist[i] + abundlist[j]] == 0: sumlist[abundlist[i] + abundlist[j]] = 1

Where I put a 1 if the sum has occurred, in order to avoid equal values. I have also tried to eliminate all multiples from the abundlist first, but that didn't help at all.

I think I may be approaching this problem wrong. Any suggestions/optimizations/comments would be very helpful.

Upvotes: 2

Views: 2634

Answers (1)

user764357
user764357

Reputation:

You don't need to initialise lists in python using the first line. And to sum every pait of digits is easy using list comprehension:

>>> x=[1,2,3,4,5,15,20]
>>> [i+j for i in x for j in x]
[2, 3, 4, 5, 6, 16, 21, 3, 4, 5, 6, 7, 17, 22, 4, 5, 6, 7, 8, 18, 23, 5, 6, 7, 8, 9, 19, 24, 6, 7, 8, 9, 10, 20, 25, 16, 17, 18, 19, 20, 30, 35, 21, 22, 23, 24, 25, 35, 40]

If you want to restrict this, you can add a simple filter to the end of the comprehension:

>>> [i+j for i in x for j in x if i+j<=30]
[2, 3, 4, 5, 6, 16, 21, 3, 4, 5, 6, 7, 17, 22, 4, 5, 6, 7, 8, 18, 23, 5, 6, 7, 8, 9, 19, 24, 6, 7, 8, 9, 10, 20, 25, 16, 17, 18, 19, 20, 30, 21, 22, 23, 24, 25]

And if they need to be unique, you can covnvert it to a set, then back to a list:

>>> list(set([i+j for i in x for j in x if i+j<=30]))
[2, 3, 4, 5, 6, 7, 8, 9, 10, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 30]

However, sets are unsorted, and the conversion back to a list may not neccessarily maintain order, so you can also sort it like so:

>>> sorted(list(set([i+j for i in x for j in x if i+j<=30])))
[2, 3, 4, 5, 6, 7, 8, 9, 10, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 30]

Regarding the efficiency of this:

Here is a fun little test that shows performing the mass sums, including casting to and from sets and lists multiple times. In essence it builds a list of numbers from 1 to 1000 (weighted more towards smaller numbers to match the numbers in the original question), then performs the sums as described above.

Building and running list, and summing it, 100 times takes under 2 seconds.

>>> timeit.timeit(
    'x=sorted(list(set([randint(1,i) for i in range(2,1000)])));z=[i+j for i in x for j in x if i+j<=500]',
    setup="from random import randint",number=100)
1.7806868553161621

Upvotes: 2

Related Questions