Efficient algorithm for calculating the sum of all k-products

Question

Suppose you are given a list L of n numbers and an integer k<n . Is there an efficient way to calculate the sum of all products of k different numbers in L ?

Take L=[1,3,4,6] and k=2 as an example. Then the number I'm looking for is

1*3 + 1*4 + 1*6 + 3*4 + 3*6 + 4*6 .

Can you imagine a way to do this, avoiding the generation of all subsets of size k ?

Answer 1

Let F (X, k, n) be the sum of k-products of the first n elements of the array X.

F (X, k, n) = F (X, k, n-1) + F (X, k-1, n-1) * X [n]

which you can solve with dynamic programming. Difficulty = O (kn).

Final conditions for F (X, k, n): When n = k F (X, k, k) = X [1] * X [2] * ... * X [n]

More details:

 F(X,1,1) = X[1] F(X,1,i) = F(X,1,i-1)+X[i] for i=2...n For j=2..n: For i = 1..k: if i<j: F(X,i,j) = F(X,i,j-1)+F(X,i-1,j-1)*X[j] else if i==j: F(X,i,j) = F(X,i-1,j-1)*X[j] else: pass 

Answer 2

Yes, there is a way. Consider a polynomial

 (X + a[0]) * (X + a[1]) * ... * (X + a[n-1]) 

Its coefficients are simply the sums of k -products, its degree is n , so you can calculate the sum of all k -products for all k simultaneously in the O (n ^ 2) steps.

After steps s coefficient at X ^sk is the sum of k -products of the first elements of s . k products of the first elements s+1 are divided into two classes: those that are associated with the element (s+1) ^st - are of the form a[s]*((k-1) -product of the first elements s ) - and those not related to this, are the k products of the first elements of s .

The code is such that result[i] is the coefficient at X ⁱ (the sum of (ni) -products):

 int *k_products_1(int *a, int n){ int *new, *old = calloc((n+1)*sizeof(int)); int d, i; old[0] = 1; for(d = 1; d <= n; ++d){ new = calloc((n+1)*sizeof(int)); new[0] = a[d-1]*old[0]; for(i = 1; i <= d; ++i){ new[i] = old[i-1] + a[d-1]*old[i]; } free(old); old = new; } return old; } 

If you only need the sum of k -products for one k , you can stop the calculation with index nk by specifying the O (n * (nk)) algorithm - this is good if k >= n/2 . To get the O (n * k) algorithm for k <= n/2 , you need to organize the array of coefficients on the contrary, so result[k] is the coefficient at X ^nk (and stop calculating at index k if you want to get only one amount):

 int *k_products_2(int *a, int n){ int *new, *old = calloc((n+1)*sizeof(int)); int d, i; old[0] = 1; for(d = 1; d <= n; ++d){ new = calloc((n+1)*sizeof(int)); new[0] = 1; for(i = 1; i <= d; ++i){ new[i] = old[i] + a[d-1]*old[i-1]; } free(old); old = new; } return old; } 

Answer 3

You can reduce k by 1:

eg. for k = 2

 1*3 + 1*4 + 1*6 + 3*4 + 3*6 + 4*6 

==

 1*(3+4+6)+3*(4+6)+4*6 

and for k = 3

 1*3*4 + 1*3*6 + 3*4*6 

==

 1*3*(4+6) + 3*4*6 

So basically you change your list and then rewrite the same algorithm with k reduced by 1 and the rest of the list

Answer 4

For k = 2,

let s = SUM_x_in_L x (sum of numbers) and sq = SUM_x_in_L x^2 (sum of squares)

then it is SUM_x_in_L (s - x) * x / 2 = (s * s - sq) / 2

Answer 5

An interesting property that you can explore is the distributive property of multiplication with respect to the addition.

 L=[a,b,c,d] 

When k = 1, it is trivial:

 S=a+b+c+d 

When k = 2:

 S = a * (b + c + d) + b * (c + d) + c * d 

When k = 3, things get a little more interesting:

 S = a * b * ( c + d) + (c * d) * (a + b) S = a * (b * (c + d)) + c * d) + b * (c * d) <-- this form lends itself better to the algorithm 

And for k = 4:

 S = a * b * c * d 

This should be done for large n.

Implementation in C #:

  private static int ComputeSum(int[] array, int offset, int K) { int S = 0; if (K == 1) { for (int i = offset; i < array.Length; i++) S += array[i]; } else if ((array.Length - offset) == K) { S = array[offset] * ComputeSum(array, offset + 1, K - 1); } else if (offset < array.Length) { S = ComputeSum(array, offset + 1, K) + array[offset] * ComputeSum(array, offset + 1, K - 1); } return S; } 

What can be further improved with memoization.

Answer 6

Algebraically, for k=2 just take the sum of the elements of L , put its square and subtract the sum of the squares of L I.e:

 int sum = 0; int sqSum = 0; for (int i=0; i<n; ++i) { sum += L[i]; sqSum += L[i]*L[i]; } return sum*sum - sqSum; 

In your example, what you calculate is

 (1 + 3 + 4 + 6)^2 - (1^2 + 3^2 + 4^2 + 6^2) = 1*3 + 1*4 + 1*6 + 3*4 + 3*6 + 4*6 

This should give you a hint on how to act in general.