从n个元素的数组中选取m个元素进行组合，计算所有组合乘积的总和

Question

假设我有一个数组 {1, 2, 5, 4}，并且 m = 3。 我需要找到：

1*2*5 + 1*2*4 + 1*5*4 + 2*5*4

即：从n个元素的数组中选择m个元素进行乘法运算并求和。

其中一种可能的解决方案是找到所有组合，然后解决它，但这将是一个O(nCm)的解决方案。是否有更好的算法？

- user3615612

---

除了这种方式，你能想象其他解决方法吗？ - Tarec

如果您想知道是否有一个公式来代替找到所有的组合,请尝试math.stackexchange.com。 - Barmar

@PhamTrung 为什么不呢？大O符号表示一个上界。 - John Dvorak

@PhamTrung 是的，我已经编辑了复杂度。 - user3615612

有一种替代的O(m n)时间复杂度算法，它使用牛顿恒等式（你正在评估第m个基本对称多项式）。 - David Eisenstat

Answer 1

这个问题等价于计算给定根（维达定理）的多项式的第M个系数。以下是Delphi中适应的算法（O（N）内存和O（N ^ 2）时间）：

 function CalcMultiComb(const A: array of Integer; const M: Integer): Integer;
  var
    i, k, N: Integer;
    Coeff: TArray<Integer>;
  begin
    N := Length(A);
    if (N = 0) or (M > N) then
      Exit;
    SetLength(Coeff, N + 1);

    Coeff[0] := -A[0];
    Coeff[1] := 1;
    for k := 2 to N do begin
      Coeff[k] := 1;
      for i := k - 2 downto 0 do
        Coeff[i + 1] := Coeff[i] - A[k-1] * Coeff[i + 1];
      Coeff[0] := -A[k-1] * Coeff[0];
    end;

    Result := Coeff[N - M];
    if Odd(N - M) then
      Result := - Result;
  end;

使用 M=1..4 调用 CalcMultiComb([1, 2, 3, 4]) 将返回结果 10、35、50 和 24。

- MBo

---

有趣的是，使用FFT进行快速多项式插值可以将复杂度提高到O(n log n)。 - Niklas B.

Answer 2

我有一个动态规划解决方案，想要分享。时间复杂度为 O(k*n^2)，其中 n 是总数。

这个想法是，我们从 0 到 k-1 开始填充每个位置。所以如果我们假设在位置 ith，要填充的数字是 a，那么以 a 开头的所有组合的总和将是 a 乘以从位置 (i+1)th 开始，以 (a+1) 开头的所有组合的总和。

注意：我已更新了解决方案，所以它可以适用于任何数组 data。我的语言是 Java，因此您可以注意到数组的索引是基于 0 的，从 0 到 n-1。

public int cal(int n, int k , int[]data){
   int [][] dp = new int[k][n + 1];
   for(int i = 1; i <= n; i++){
       dp[k - 1][i] = data[i - 1];
   }
   for(int i = k - 2; i >= 0; i--){
       for(int j = 1 ; j <= n; j++){
           for(int m = j + 1 ; m <= n; m++){
               dp[i][j] += data[j - 1]*dp[i + 1][m];
           }
       }
   }
   int total = 0;
   for(int i = 1; i <= n; i++){
       total += dp[0][i];
   }
   return total;
}

- Pham Trung

---

@JanDvorak 是的，天真的方法是O((n!)/(k!)(n-k)!)，这是多项式O(k*n^2)。 - Pham Trung

抱歉，我误读指数为某个参数的指数。 - John Dvorak

这个解决方案仅适用于元素为等差数列，公差为1且第一个元素为1的数组吗？ - user3615612

@JanDvorak 没问题 :) - Pham Trung

为什么是O(k * n^2)？实现O(k * n)很简单，使用状态f(i, j)=前i个元素中所有大小为j的子集的乘积和。然后我们有f(i, j) = f(i-1, j-1) * a[i] + f(i-1, j)，这是O(1)的转移。 - Niklas B.

@NiklasB。是的，正确的 :) 我会找时间修改我的答案。 - Pham Trung

Answer 3

我也遇到了同样的问题。我也是通过Vieta算法找到了解决方法。我对算法进行了微调，不计算不需要的多项式系数。这个复杂度为O(N*M)。我研究过DFT和FFT，但如果M足够小，这种方法甚至比快速傅里叶变换算法更快。这是Java语言。

public BigInteger sumOfCombMult(Integer[] roots, int M)
{
    if (roots.length < M)
    {
        throw new IllegalArgumentException("size of roots cannot be smaller than M");
    }

    BigInteger[] R = new BigInteger[roots.length];

    for (int i = 0; i < roots.length; i++)
    {
        R[i] = BigInteger.valueOf(roots[i]);
    }

    BigInteger[] coeffs = new BigInteger[roots.length + 1];

    coeffs[0] = BigInteger.valueOf(roots[0]);

    int lb = 0;

    for (int i = 1; i < roots.length; i++)
    {
        lb = Math.max(i - M, 0);

        coeffs[i] = R[i].add(coeffs[i - 1]);

        for (int j = i - 1; j > lb; j--)
        {
            coeffs[j] = R[i].multiply(coeffs[j]).add(coeffs[j - 1]);

        }

        if (lb == 0)
        {
            coeffs[0] = coeffs[0].multiply(R[i]);
        }
    }

    return coeffs[roots.length - M];
}

- Hayati Guvence