Suma del producto sobre todas las combinaciones con un elemento de cada grupo

Question

Dado que tengo conjuntos distintos m no vacías (Z marcado [1], Z [2], ..., Z [m]), mi objetivo para calcular la suma de todos los subconjuntos posibles, donde hay exactamente una elemento de cada conjunto. El tamaño de cada subconjunto se define para ser el producto de sus miembros. Por ejemplo:

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

Z[ 2 ] = {4,5}

Z[ 3 ] = {7,8}

En caso de resultar en:

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

Si bien esto es fácil de código (en cualquier idioma), se trata de una actualización del famoso suma subconjunto problema? Si no es así, por favor proporcione un algoritmo de tiempo polinomial que calcula esta suma (pseudo-código o pitón preferido!). Si no existe un algoritmo de tiempo polinomial explique por qué.

Answer 1

Es 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

¿Cuál es la función de Python como suma (), pero para la multiplicación ? producto ()?

Yo personalmente creo que Guido hizo una terrible decisión con respecto 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