7

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.)

Lafexlos
  • 7,618
  • 5
  • 38
  • 53
blackened
  • 861
  • 10
  • 19

4 Answers4

10

Use itertools.combinations

>>> l = [1, 2, 3, 4]
>>> sum([i*j for i,j in list(itertools.combinations(l, 2))])
35
Remi Guan
  • 21,506
  • 17
  • 64
  • 87
Avinash Raj
  • 172,303
  • 28
  • 230
  • 274
  • 1
    I cannot decide which answer to choose as “the answer”. Is Kevin’s approach superior in any way? (Perhaps in a more general setting or whatever.) – blackened Dec 23 '15 at 14:12
  • Shouldn't it be `sum([i*j for i,j in list(combinations(l, 2))])`? – Joe T. Boka Dec 23 '15 at 14:13
  • @blackened: If I was you, I'd accept Avinash's answer, since he's answer is clear and simple than mine. I think my answer was just used more function instead of `*` operator, it doesn't faster than Avinash, but more complex. – Remi Guan Dec 23 '15 at 14:16
  • @JoeR: Nope, no need create another list here. – Remi Guan Dec 23 '15 at 14:16
  • 1
    @kevin previous code of mine is fater than the current one. Since I heared that, gen expresion takes more no of loops than list. – Avinash Raj Dec 23 '15 at 14:16
  • @KevinGuan I am not talking about the list, I mean taking out the `itertools.` and just use `combinations(l, 2)` like so: `sum(i*j for i, j in combinations(l, 2))` – Joe T. Boka Dec 23 '15 at 14:18
  • @JoeR then the import stmt should look like `from itertools import combinations`, but it isn't an issue.. – Avinash Raj Dec 23 '15 at 14:20
  • @AvinashRaj: Well, I don't know that :(. However I tested and rollbacked, I'll go to search about it. – Remi Guan Dec 23 '15 at 14:22
  • @AvinashRaj yes! That's how I imported it. My bad! – Joe T. Boka Dec 23 '15 at 14:23
7
>>> 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.

Community
  • 1
  • 1
Remi Guan
  • 21,506
  • 17
  • 64
  • 87
  • 1
    You can also use `itertools.starmap` in place of `reduce`: `sum(itertools.starmap(operator.mul, itertools.combinations(l, 2)))`. – chepner Dec 23 '15 at 14:16
3

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.

manishrw
  • 429
  • 5
  • 17
1

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 like this:

# 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
Steve Misuta
  • 1,033
  • 7
  • 7