algorithm - 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) 解决方案。有没有更好的算法？

Answer 1

此问题等同于计算具有给定根的多项式的第 M 个系数 (Vieta's theorem)。 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], M) 给出结果 10, 35, 50, 24