The sum of the product combinations in the list

Question

What is the Python way of summing up the product of all the combinations in a given list, for example:

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

(In this example, I took all two-element combinations, but it could be different.)

Answer 1

Use itertools.combinations

 >>> l = [1, 2, 3, 4] >>> sum([i*j for i,j in list(itertools.combinations(l, 2))]) 35 

Answer 2

 >>> 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 evaluates the function using arguments derived from iterable. It is used instead of map() when the argument parameters are already grouped into tuples from one iterable (the data was "pre-encoded").

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

Answer 3

I'm not sure about the pythonic way, but you can solve this problem in a simpler way.

eg. The list of results [a, b, c] => can also be written as

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

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

In python, you can achieve the same as below:

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

PS I know that the problem can be solved using itertools, and the question specifically requires a pythonic solution to solve it. I think it would be easy to do this without having tried all the combinations.

Answer 4

This is also the sum of the upper triangle of the outer vector product of the array with itself:

 import numpy as np np.triu(np.outer([1,2,3,4],[1,2,3,4]),1).sum() 35 

Step by step, it works as follows:

 # outer product np.outer([1,2,3,4],[1,2,3,4]) array([[ 1, 2, 3, 4], [ 2, 4, 6, 8], [ 3, 6, 9, 12], [ 4, 8, 12, 16]]) # upper triangle np.triu(np.outer([1,2,3,4],[1,2,3,4]),1) array([[ 0, 2, 3, 4], [ 0, 0, 6, 8], [ 0, 0, 0, 12], [ 0, 0, 0, 0]]) # then the sum, which is the non-zero elements np.triu(np.outer([1,2,3,4],[1,2,3,4]),1).sum() 35