Вопросы Теги

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

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

В качестве примера возьмем L = [1,3,4 , 6] и k = 2 . Тогда число, которое я ищу, будет

1 * 3 + 1 * 4 + 1 * 6 + 3 * 4 + 3 * 6 + 4 * 6 .

Можете ли вы придумать способ сделать это, чтобы избежать создания всех подмножеств размера k ?

7
задан The Unfun Cat 5 October 2012 в 18:33
поделиться