子集的积和

问题内容：

此操作有名称吗？并且：是否有封闭形式的表达式？

对于给定的一组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代码。（如果您想提供示例实现，则任何语言都是说明性的。）

问题答案：

这些是基本对称多项式。您可以像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），但是我懒得编写该代码。

子集的积和

微信关注