Эффективный алгоритм для расчета суммы всех k-произведений

Question

Предположим, вам дан список L из n чисел и целое число k<n.Существует ли эффективный способ вычисления суммы всех произведений k различных чисел в L?

В качестве примера возьмем 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) - сумма k-произведений первых n элементов массива X.

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 -произведений для всех k одновременно в O (n ^ 2) шагов.

После s шагов, коэффициент X ^sk является суммой k -произведений первого sэлементы массива.k -продукты первых s+1 элементов делятся на два класса, включая (s+1) ^st - они имеют форму a[s]*((k-1) -продукта первых s элементов)- и те, кто его не задействует - это k -продукты первых s элементов.

Код такой, что result[i] является коэффициентом X ⁱ (суммаиз (n-i) -продукции):

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, вы можете остановить вычисление по индексу n-k, даваяАлгоритм O (n * (nk)) - это хорошо, если k >= n/2.Чтобы получить алгоритм O (n * k) для k <= n/2, необходимо организовать массив коэффициентов наоборот, чтобы 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

Алгебраически, для 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

Это должно дать вам подсказку о том, как действовать в целом.

Answer 4

Интересным свойством, которое вы можете исследовать, является свойство распределения умножения относительно сложения.

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 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 на 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 и только остальной частью списка