子集的积和

这个操作有名字吗？并且：是否存在封闭式表达式？

• 对于给定的 n 个元素集合，k 值介于 1 和 n 之间，
• 获取 k 个项目的所有子集（组合）
• 求每个子集的乘积
• 求所有这些乘积的总和

我可以用 Python 表达这一点，并且很容易地进行计算：

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

我只是在寻找闭合形式表达式，以避免在集合大小变大时出现循环。

请注意，这与这个问题不同：每组中一个元素的所有组合的乘积之和——这个问题是关于笛卡尔积的乘积和。我正在寻找大小为 k 的组合集合的乘积和；我不认为它们是一样的。

明确地说，对于 set(a, b, c, d)，则：

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

只是寻找表达方式；无需专门提供Python代码。 （如果您想提供示例实现，任何语言都可以说明。）

这些都是初等对称多项式。您可以使用维基百科中的求和符号来书写它们。您还可以使用维埃塔的公式一次获取所有它们作为多项式的系数（最多符号）

(x-a_1)(x-a_2)...(x-a_k) =
   x^k -
   (a_1 + ... + a_k) x^(k-1) +
   (a_1 a_2 + a_1 a_3 + ... + a_(k-1) a_k)) x^(k-2) +
   ... +
   (-1)^k a_1 ... a_k

通过展开 (x-a_1)(x-a_2)...(x-a_k)，您将获得一个多项式时间算法来计算所有这些数字（您的原始实现以指数时间运行）。

编辑：Python实现：

from itertools import izip, chain

l = [2,3,4]

x = [1]    
for i in l:
    x = [a + b*i for a,b in izip(chain([0],x), chain(x,[0]))]
print x

得到 [24, 26, 9, 1]，如 2*3*4=24, 2*3+2*4+3*4=26, 2+3+4=9。最后一个 1 是空乘积，对应于您的实现中的 k=0。

This should be O(N²). Using polynomial FFT you could do O(N log² N), but I am too lazy to code that.