各グループからの1つの要素との全ての組み合わせに応じた生成物の和

Question

iがm非空の異なるセット（標識されたZ [1]、Z [2]、...、Z [M]）、私は正確に一つがある場合、すべての可能なサブセットの和を計算することを目指していることを考えると各セットからの要素。各サブセットのサイズは、そのメンバーの積であると定義されます。たとえばます：

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

これは、（任意の言語で）コードすることは容易であるが、

、これは有名なサブセット和の言い換えであります問題の？ない場合は、（擬似コードやPythonが好ましく！）この合計を計算し、多項式時間アルゴリズムを提供してください。何の多項式時間アルゴリズムが存在しない場合は理由を説明してくださいます。

Answer 1

これはそれを見ることは容易である（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

サムのようなPythonの関数は（何）が、乗算のため？製品（）は

私は個人的にグイドはMULに関する恐ろしい決断をしたと思います。

Answer 2

>>> z1 = [1, 2, 3]
>>> z2 = [4, 5]
>>> z3 = [7, 8]
>>> s = 0
>>> for a in z1:
        for b in z2:
            for c in z3:
                s += a*b*c      
>>> s
810