Сумма произведений подмножеств
Есть ли название для этой операции? И: есть ли выражение в закрытой форме?
Для данного набора из n элементов и значения k от 1 до n,Взять все подмножества (комбинации) из k предметовНайти продукт каждого подмножестваНайти сумму всех этих продуктовЯ могу выразить это в Python, и сделать расчет довольно легко:
<code>from operator import mul from itertools import combinations from functools import reduce def sum_of_product_of_subsets(list1, k): val = 0 for subset in combinations(list1, k): val += reduce(mul, subset) return val </code>
Я просто ищу выражение закрытой формы, чтобы избежать цикла в случае большого размера набора.
Обратите внимание, что это НЕ то же самое, что этот вопрос:Сумма товара по всем комбинациям с одним элементом из каждой группы - этот вопрос о сумме произведений декартовых произведений. Я ищу сумму произведений набора комбинаций размера k; Я не думаю, что они одинаковы.
Чтобы было понятно, для множества (a, b, c, d) тогда:
<code>k = 4 --> a*b*c*d k = 3 --> b*c*d + a*c*d + a*b*d + a*b*c k = 2 --> a*b + a*c + a*d + b*c + b*d + c*d k = 1 --> a + b + c + d </code>
Просто ищу выражение; нет необходимости специально указывать код Python. (Любой язык будет иллюстративным, если вы хотите привести пример реализации.)