Algoritmo eficiente para calcular la suma de todos los productos k

Question

Supongamos que se le proporciona una lista L de n números y un número entero k<n. ¿Hay una manera eficiente de calcular la suma de todos los productos de k números distintos en L? Por ejemplo, tome L=[1,3,4,6] y k=2. Entonces el número que estoy buscando es

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

¿Puede pensar en una forma de hacerlo que evite generar todos los subconjuntos de tamaño k?

Answer 1

Sea F (X, k, n) ser la suma k-producto de los primeros n elementos de matriz X.

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

que puede resolver mediante programación dinámica. Complejidad = O (kn).

Condiciones de finalización para F (X, k, n): cuando n = k F (X, k, k) = X [1] * X [2] * ...* X [n]

Más detalles:

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

Sí, hay una manera. Considere el polinomio

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

sus coeficientes son sólo las sumas de los k -productos, su grado es n, para que pueda calcular la suma de todos los k -productos para todos k simultáneamente en O (n^2) pasos .

Después s pasos, el coeficiente de X ^s-k es la suma de los k -productos de los primeros s elementos de matriz. Los k -productos de los primeros s+1 elementos se dividen en dos clases, los que implican la elemento (s+1)^{st - estos tienen la -producto forma a[s]*((k-1) de los primeros s elementos) - y los que no implica que - estos son los k -productos de los primeros elementos s.}

Código de tal manera que result[i] es el coeficiente de X ⁱ (la suma de los (n-i) -productos):

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; 
} 

Si sólo desea que la suma de los k -productos para una k, puede detener el cálculo en el índice n-k, dando un algoritmo O (n * (nk)) - eso es bueno si k >= n/2. Para obtener un algoritmo O (n * k) para k <= n/2, debe organizar la matriz de coeficientes a la inversa, de modo que result[k] sea el coeficiente de X ^nk (y detenga el cálculo en el índice k si solo desea una suma):

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

puede reducir k por 1:

por ejemplo,para k = 2

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

==

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

y para k = 3

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

==

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

Así que básicamente el ciclo de su lista, a continuación, Recurse al mismo algoritmo con k reducido en 1 y solo el resto de la lista

Answer 4

Para k = 2,

nos dejó s = SUM_x_in_L x (suma de los números) y sq = SUM_x_in_L x^2 (suma de los cuadrados)

entonces es SUM_x_in_L (s - x) * x/2 = (s * s - sq)/2

Answer 5

Una propiedad interesante que podría explorar es la propiedad distributiva de multiplicación en relación a la suma.

L=[a,b,c,d] 

Cuando k = 1, es trivial:

S=a+b+c+d 

Cuando k = 2:

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

Cuando k = 3, las cosas se ponen un poco más interesante:

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 

Y para k = 4:

S = a * b * c * d 

Esto debería ser válido para valores mayores de n.

Una implementación en 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; 
} 

que pueden mejorarse aún más por memoization.

Answer 6

algebraicamente, por k=2 acaba de tomar la suma de los elementos de L, cuadrado, y restar la suma de los cuadrados de L. Es decir:

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; 

En su ejemplo, lo que se está calculando es este

(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 

Esto debería dar una pista sobre cómo proceder en general.