计算所有 k 乘积之和的高效算法

Question

假设给您一个由 n 个数字组成的列表 L 和一个整数 k。有没有一种有效的方法来计算L中k个不同数字的所有乘积之和？

以 L=[1,3,4,6] 和 k=2 为例。那么我要查找的数字是

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

你能想出一种方法来避免生成所有大小为 k 的子集吗？

Answer 1

令 F(X,k,n) 为数组 X 的前 n 个元素的 k 乘积和。

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

您可以使用动态规划来解决。复杂度 = O(kn)。

F(X,k,n) 的结束条件： 当 n=k F(X,k,k) = X[1]* X[2]*...*X[n]

更多详细信息：

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

是的，有办法。考虑多项式

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

它的系数只是k乘积的总和，其次数为n，因此您可以计算所有k的总和-在 O(n^2) 步中同时计算所有 k 的产品。

经过s步后，X^sk的系数是第一个s数组的k乘积之和元素。前 s+1 元素的 k 乘积分为两类，涉及 (s+1)^{st< /sup> 元素 - 这些具有形式 a[s]*((k-1) - 第一个 s 元素的乘积) - 以及那些不涉及它的 - 这些是第一个的 k 个乘积s 元素。}

代码使得 result[i] 是 Xⁱ 的系数（(ni)-乘积之和）：

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

如果您只想一个 k 的 k 乘积之和，您可以在索引 nk 处停止计算，给出 O(n*(nk) ) 算法 - 如果 k >= 就很好n/2。要获得 k <= n/2 的 O(n*k) 算法，您必须以相反的方式组织系数数组，以便 result[k] 是 X^nk 的系数（如果您只需要一个和，则在索引 k 处停止计算）：

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

您可以探索的一个有趣的属性是乘法相对于加法的分配属性。

L=[a,b,c,d]

当 k = 1 时，这是微不足道的：

S=a+b+c+d

当 k = 2 时：

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

当 k = 3 时，事情会变得更有趣：

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

对于 k = 4： 对于

S = a * b * c * d

较大的 n 值，这应该成立。

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

可以通过记忆进一步改进。

Answer 4

您可以将 k 减少 1：

例如，对于 k=2

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

==

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

和 k=3

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

==

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

所以基本上您循环列表，然后递归到相同的算法，其中 k 减少 1 并且仅列表的其余部分

Answer 5

对于 k=2，

让我们 s = SUM_x_in_L x （数字之和）和 sq = SUM_x_in_L x^2 （平方和）

，那么它就是 SUM_x_in_L ( s - x) * x / 2 = (s * s - sq) / 2

Answer 6

从代数角度来说，对于k=2，只需取L 的元素之和，平方，然后减去L 的平方和。也就是说：

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;

在您的示例中，您正在计算的是这个

(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

这应该会提示您一般如何进行。