子集的乘积和

Question

这个操作有名字吗？而且:有一个封闭形式的表达吗？

• 对于给定的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代码.(如果您想提供示例实现,任何语言都是说明性的.)

Answer 1

这些是基本对称多项式.您可以使用维基百科中的求和符号来编写它们.您还可以使用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.最后一个是空产品,在您的实现中对应于k = 0.

这应该是O(N ²).使用多项式FFT你可以做O(N log ² N),但我懒得编码.

Answer 2

我在其他地方遇到了同样的问题,我可能会有一个更简单的解决方案.基本上你正在寻找的封闭形式就是这样:

(1 + e_1)*(1 + e_2)*(1 + e_3)*...*(1 + e_n) - 1

在考虑集合S = {e_1,e_2,...,e_n}的情况下

原因如下:

让'm'成为S元素的乘积(n = e_1*e_2*...*e_n).
如果你看一下子集元素的原始产品,你可以看到,所有这些产品都是'm'的除数.
现在将Divisor函数应用于'm'(从现在开始称为sigma(m))并进行一次修改:将所有e_i元素视为'primes'(因为我们不希望它们被分割),所以这给出了sigma(e_i )= e_i + 1.

然后,如果你将sigma应用于m:

sigma(m)=sigma(e_1*e_2*...*e_n)=1+[e_1+e_2+...+e_n]+[e_1*e_2+e_1*e_3+...+e_(n-1)*e_n]+[e_1*e_2*e_3+e_1*e_2*e_3+...+e_(n-2)]+...+[e_1*e_2*...*e_n]

这就是最初的问题.(除了开头的1).我们的除数函数是乘法的,所以前面的等式可以改写如下:

sigma(m)=(1+e_1)*(1+e_2)*(1+e_3)*...*(1+e_n)
这里有一个你需要的修正.这是因为空子集(这里考虑了它,但在原始问题中它不存在),其中包括总和中的'1'(在第一个方程的开头).所以封闭的形式,你需要的是:
(1+e_1)*(1+e_2)*(1+e_3)*...*(1+e_n) - 1

对不起,我无法真正编写代码,但我认为计算不应超过2n-1个循环.

(您可以在此处阅读有关除数函数的更多信息:http://en.wikipedia.org/wiki/Divisor_function)