Sum of multiplication of all combination of m element from an array of n elements

Question

Suppose I have an array {1, 2, 5, 4} and m = 3. I need to find:

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

i.e Sum of multiplication of all combination of m element from an array of n elements.

One of the solution possible is to find all combination and then solving it but that would be O(nCm) solution. Is there any better algorithm?

Answer 1

This problem is equivalent to calculation of Mth coefficient of polynom with given roots (Vieta's theorem). Adapted algorithm in Delphi (O(N) memory and O(N^2) time):

 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;

calls CalcMultiComb([1, 2, 3, 4], M) with M=1..4 give results 10, 35, 50, 24

Answer 2

I have a Dynamic programming solution in my mind, just want to share. Time complexity is O(k*n^2) with n is total number.

The idea is, we start to fill in each position from 0 to k -1. So if we assume at position ith, the number to be filled for this position is a, so the sum of all combination start with a will be a times the total of all combination from position (i + 1)th starting with (a + 1)

Note: I have updated the solution, so it can work with any array data, My language is Java, so you can notice that the index for array is 0 based, which start from 0 to 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;
}