Soma do produto em todas as combinações com um elemento de cada grupo

Question

Dado que eu tenho me conjuntos distintos não vazios (rotulados z [1], z [2], ..., z [m]), pretendo calcular a soma de todos os subconjuntos possíveis onde existe exatamente um elemento de cada definir. O tamanho de cada subconjunto é definido como o produto de seus membros. Por exemplo:

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

Z[ 2 ] = {4,5}

Z[ 3 ] = {7,8}

Deve resultar em:

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

Embora isso seja fácil de codificar (em qualquer idioma), isso é uma reformulação do famoso Problema da soma do subconjunto? Caso contrário, forneça um algoritmo de tempo polinomial que calcule essa soma (pseudo-código ou Python preferido!). Se nenhum algoritmo de tempo polinomial existir, explique o porquê.

Answer 1

É fácil ver que (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

Qual é a função python como sum (), mas para multiplicação? produtos()?

Pessoalmente, acho que Guido tomou uma decisão terrível sobre 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