Sum all unique pair differences in a vector

Question

I have the following problem: given a vector x of length n, find all but sum of unique pairwise differences of the vector elements.
One should not consider the pairs where the operands are merely exchanged, just one of them (e.g. do not consider (x_i - x_j) if (x_j - x_i) was computed).

For example:

v = [4, 2, 1, 5]

Sum: (4-2) + (4-1) + (4-5) + (2-1) + (2-5) + (1-5)

It is very easy to do this with two nested for loops. I need this to be computed very efficiently in Python since each such sum is then used together with a very large and sparse matrix. I am repeatedly processing the vectors with sizes of tens of thousands elements.

Is there a more elegant approach? In R one could use the outer function where instead of multiplication, use difference operator, then take upper tridiagonal part of matrix and compute sum of the resulting matrix.

Answer 1

If I understand your question correctly, the kth element is added (n - 1 - 2 * k) times, where n is the length of the array. So you can just do this:

v = [4, 2, 1, 5]

n = len(v)
s = 0 # this is going to be the sum
for idx, x in enumerate(v):
    s += (n - 1 - 2 * idx) * x
print s

Answer 2

you can use itertools.combinations and map() function :

sum(map(lambda x :x[0]-x[1] ,combinations(v,2)))

Demo :

>>> from itertools import combinations
>>> from operator import sub
>>> list(combinations(v,2))
[(4, 2), (4, 1), (4, 5), (2, 1), (2, 5), (1, 5)]
>>> [sub(i,j) for i,j in list(combinations(v,2))]
[2, 3, -1, 1, -3, -4]
>>> sum([sub(i,j) for i,j in list(combinations(v,2))])
-2