Sum of the product over all combinations with one element from each group

Question

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}

Should result in:

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

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.

Answer 1

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

http://stackoverflow.com/questions/595374/whats-the-python-function-like-sum-but-for-multiplication

I personally think that Guido made a terrible decision regarding 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