Sum of products of pairs in a list

Question

This is the problem I have. Given a list

xList = [9, 13, 10, 5, 3]

I would like to calculate for sum of each element multiplied by subsequent elements

sum([9*13, 9*10, 9*5 , 9*3]) + 
sum([13*10, 13*5, 13*3]) + 
sum([10*5, 10*3]) + 
sum ([5*3])

in this case the answer is 608.

Is there a way to do this perhaps with itertools or natively with numpy?

Below is a function I came up with. It does the job but it is far from ideal as I would like to add other stuff as well.

    def SumProduct(xList):
        ''' compute the sum of the product 
        of a list 
        e.g. 
        xList = [9, 13, 10, 5, 3]
        the result will be 
        sum([9*13, 9*10, 9*5 , 9*3]) + 
        sum([13*10, 13*5, 13*3]) + 
        sum([10*5, 10*3]) + 
        sum ([5*3])
        '''
        xSum = 0
        for xnr, x in enumerate(xList):
            #print xnr, x
            xList_1 = np.array(xList[xnr+1:])
            #print x * xList_1
            xSum = xSum + sum(x * xList_1)
        return xSum

Any help appreciated.

N.B: In case you wonder, I am trying to implement Krippendorf's alpha with pandas

Answer 1

x = array([9, 13, 10, 5, 3])
result = (x.sum()**2 - x.dot(x)) / 2

This takes advantage of some mathematical simplifications to work in linear time and constant space, compared to other solutions that might have quadratic performance.

Here's a diagram of how this works. Suppose x = array([2, 3, 1]). Then if you view the products as the areas of rectangles:

x is this stick: -- --- -

x.sum()**2 is this rectangle:
   -- --- -
  |xx xxx x
  |xx xxx x

  |xx xxx x
  |xx xxx x
  |xx xxx x

  |xx xxx x

x.dot(x) is this diagonal bit:
   -- --- -
  |xx
  |xx

  |   xxx
  |   xxx
  |   xxx

  |       x

(x.sum()**2 - x.dot(x)) is the non-diagonal parts:
   -- --- -
  |   xxx x
  |   xxx x

  |xx     x
  |xx     x
  |xx     x

  |xx xxx

and (x.sum()**2 - x.dot(x)) / 2 is the product you want:
   -- --- -
  |   xxx x
  |   xxx x

  |       x
  |       x
  |       x

  |