Soma do produto em todas as combinações com um elemento de cada grupo
Pergunta
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ê.
Solução
É 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.
Outras dicas
>>> 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