9

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

  • 对于给定的 n 个元素集合，以及介于 1 和 n 之间的 k 值，
  • 取 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 代码。（如果您想提供示例实现，任何语言都可以说明。）

4

2 回答 2

12

这些是基本的对称多项式。您可以使用 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)，但我懒得写代码。

于 2012-04-11T12:56:52.467 回答
6

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

(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”的除数。
现在将除数函数应用于“m”（从现在起称为 sigma(m) ），只需进行一项修改：将所有 e_i 元素视为“素数”（因为我们不希望它们被除），所以这给出了 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 ）

于 2014-02-03T19:59:08.600 回答