Somma del prodotto su tutte le combinazioni con un elemento di ogni gruppo

Question

Dato che ho m distinti insiemi non vuoti (marcato Z [1], Z [2], ..., Z [m]), che hanno lo scopo di calcolare la somma di tutti i possibili sottoinsiemi dove c'è esattamente un elemento da ogni insieme. La dimensione di ciascun sottoinsieme è definito come il prodotto dei suoi membri. Ad esempio:

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

Z[ 2 ] = {4,5}

Z[ 3 ] = {7,8}

Dovrebbe risultare 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

Mentre questo è facile da codice (in qualsiasi lingua), è presente una riaffermazione dei famosi href="http://en.wikipedia.org/wiki/Subset_sum_problem" somma sottoinsieme problema ? In caso contrario, si prega di fornire un algoritmo polinomiale che calcola questa somma (pseudo-codice o python preferito!). Se non esiste alcun algoritmo di tempo polinomiale si prega di spiegare perché.

Answer 1

È facile vedere che (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 è la funzione Python come sum (), ma per la moltiplicazione ? prodotto ()?

Personalmente ritengo che Guido ha preso una decisione terribile per quanto riguarda 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