此操作有名称吗？并且：是否有封闭形式的表达式？
我可以用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代码。（如果您想提供示例实现，则任何语言都是说明性的。）
这些是基本对称多项式。您可以像Wikipedia一样使用求和符号来编写它们。您还可以使用Vieta的公式一次获取所有多项式作为多项式的系数（最多为符号）
(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。
这应该是O（N 2）。使用多项式FFT可以执行O（N log 2 N），但是我懒得编写该代码。
