Сумма умножения всей комбинации m элементов из массива n элементов

algorithm

2538 просмотра

3 ответа

Предположим, у меня есть массив {1, 2, 5, 4}и m = 3. Мне нужно найти:

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

т.е. сумма умножения всех комбинаций m элементов из массива из n элементов.

Одно из возможных решений - найти все комбинации и затем решить их, но это было бы O(nCm)решением. Есть ли лучший алгоритм?

Автор: user3615612 Источник Размещён: 12.11.2019 09:39

Ответы (3)


5 плюса

Эта задача эквивалентна вычислению 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;

вызовы CalcMultiComb ([1, 2, 3, 4], M) с M = 1..4 дают результаты 10, 35, 50, 24

Автор: MBo Размещён: 08.05.2014 09:29

4 плюса

Я имею в виду решение для динамического программирования, просто хочу поделиться. Временная сложность 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 Размещён: 08.05.2014 09:19

2 плюса

Я придумал ту же проблему. Я нашел решение и с помощью алгоритма Виеты. Я доработал алгоритм не для расчета коэффициента полинома, который не нужен. Сложность O (N * M). Я изучил ДПФ и БПФ, но если 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 Размещён: 23.12.2014 11:16
Вопросы из категории :
32x32