Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Sum of product of combinations in a list

What is the Pythonic way of summing the product of all combinations in a given list, such as:

[1, 2, 3, 4]
--> (1 * 2) + (1 * 3) + (1 * 4) + (2 * 3) + (2 * 4) + (3 * 4) = 35

(For this example I have taken all the two-element combinations, but it could have been different.)

like image 632
blackened Avatar asked Dec 23 '15 13:12

blackened


3 Answers

Use itertools.combinations

>>> l = [1, 2, 3, 4]
>>> sum([i*j for i,j in list(itertools.combinations(l, 2))])
35
like image 127
Avinash Raj Avatar answered Oct 19 '22 01:10

Avinash Raj


>>> a = [1, 2, 3, 4]    
>>> import operator
>>> import itertools
>>> sum(itertools.starmap(operator.mul, itertools.combinations(l, 2)))
35

itertools.combinations(a, 2) returns:

>>> list(itertools.combinations(a, 2))
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
>>> 

And itertools.starmap() does:

Make an iterator that computes the function using arguments obtained from the iterable. Used instead of map() when argument parameters are already grouped in tuples from a single iterable (the data has been “pre-zipped”).

Finally, use sum() with a generator comprehension to get the final results.

like image 31
Remi Crystal Avatar answered Oct 18 '22 23:10

Remi Crystal


I'm not sure about the pythonic way, but you could resolve this problem into a simpler one.

E.g. For a list [a, b, c] => result can also be written as

( (a + b + c)^2 - (a^2 + b^2 + c^2) ) / 2

So, it can be written as difference of square of sum of list and sum of squares of list, divided by 2.

You can achieve the same as follows in python:

a = [1,2,3,4]
( (sum(a) ** 2) - sum([x ** 2 for x in a]) ) / 2

P.S. I know the problem can be solved using itertools and question specifically asks for pythonic way to solve it. I think it would be much easy to do it without trying out all combinations.

like image 33
manishrw Avatar answered Oct 19 '22 00:10

manishrw