Converting combinations of integers into list of sums of these combinations

Question

I need to do this: I have list of integers, i make all possible combinations containing 3 of these numbers, and output is list containing sums of these combinations. (not sum of all combinations together, but for each combination one sum)

My algorithm do it in this way: make list of all possible combinations, then count sum of each combination and save it into list, what is too uneffective if number of integers is large. Here is little sample in python:

import itertools

array=[1,2,3,4]
combs=[] 

els = [list(x) for x in itertools.combinations(array, 3)]
combs.extend(els) 
result=list(map(sum, combs))

Could you please come up with some more effective solution? Maybe if there is some way of making it a loop where there isn't made a list of combinations at first and counted sum of each combination at second but rather it straight counts sum of just created combination, saves it into list and then continues to another one until all combinations and sums are done.

Why don’t you just go straight to [sum(x) for ...]? Converting the tuples to lists, then the list of lists to a new list of lists, then to another new list of integers, seems completely pointless. — jonrsharpe
You cannot make this efficient for large n without eliminating the "combinations" component. That is inefficient by nature (see combinatorial explosion) You need a different approach to your problem. But for that, you need to define your problem first. — ayhan
It's better if you can avoid making a list. See if you can reorganize your logic so that you can operate on each sum as it's produced. Eg, for s in map(sum, combinations(array, 3)): do_stuff(s) — PM 2Ring

Eugene Yarmash Eugene Yarmash · Accepted Answer · 2017-10-08T22:26:12

sum() works with any iterable, not just lists. You could make the code more efficient by applying it directly to the combinations' tuples:

result = [sum(c) for c in itertools.combinations(array, 3)]

If you want to process the result lazily, you can use a generator expression as well:

result = (sum(c) for c in itertools.combinations(array, 3))

Converting combinations of integers into list of sums of these combinations

1 Answers