将产物在所有组合从每个组中的一个元素总和 [英] Sum of the product over all combinations with one element from each group

问题描述

考虑到我有m个非空不同组（标记为Z [1]，Z [2]，...，Z [M]），我的目标是计算所有可能子集的总和，其中恰好有一个元件从每个集。每个子集的大小被定义为其成员的产物。例如：

Given that I have m non-empty distinct sets (labeled Z[ 1 ], Z[ 2 ], ..., Z[ m ]), I aim to compute the sum of all possible subsets where there is exactly one element from each set. The size of each subset is defined to be the product of its members. For example:

Z [1] = {1,2,3}

Z [2] = {4,5}

Z [3] = {7,8}

应该产生：

1 * 4 * 7 + 1 * 4 * 8 + 1 * 5 * 7 + 1 * 5 * 8 + 2 * 4 * 7 + 2 * 4 * 8 + 2 * 5 * 7 + 2 * 5 * 8 + 3 * 4 * 7 + 3 * 4 * 8 + 3 * 5 * 7 + 3 * 5 * 8 = 810

1*4*7 + 1*4*8 + 1*5*7 + 1*5*8 + 2*4*7 + 2*4*8 + 2*5*7 + 2*5*8 + 3*4*7 + 3*4*8 + 3*5*7 + 3*5*8 = 810

虽然这是很容易code（在任何语言），这是著名的子集和问题？如果没有，请提供一个多项式时间的算法，计算这笔款项（伪code或Python preferred！）。如果没有多项式时间算法存在，请说明原因。

While this is easy to code (in any language), is this a restatement of the famous subset sum problem? If not, please provide a polynomial time algorithm that computes this sum (pseudo-code or python preferred!). If no polynomial time algorithm exists please explain why.

推荐答案

这是很容易看到，（1 + 2 + 3）*（4 + 5）*（7 + 8）= 810。

It is easy to see that (1 + 2 + 3) * (4 + 5) * (7 + 8) = 810.

>>> from operator import mul
>>> from functools import reduce
>>> z = [{1,2,3}, {4,5}, {7,8}]
>>> s = reduce(mul, (sum(zz) for zz in z))
>>> s
810

<一个href="http://stackoverflow.com/questions/595374/whats-the-python-function-like-sum-but-for-multiplication">http://stackoverflow.com/questions/595374/whats-the-python-function-like-sum-but-for-multiplication

我个人认为，圭多方面取得MUL一个可怕的决定。

I personally think that Guido made a terrible decision regarding mul.

这篇关于将产物在所有组合从每个组中的一个元素总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！