Somme du produit sur toutes les combinaisons avec un élément de chaque groupe

Question

Comme je l'ai m ensembles distincts non vides (marqué Z [1], Z [2], ..., Z [m]), je cherche à calculer la somme de tous les sous-ensembles possibles où il y a exactement une élément de chaque ensemble. La taille de chaque sous-ensemble est défini comme étant le produit de ses membres. Par exemple:

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

Z[ 2 ] = {4,5}

Z[ 3 ] = {7,8}

devrait aboutir à:

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

Bien que ce soit facile à coder (dans toutes les langues), est-ce un retraitement des célèbres problème ? Dans le cas contraire, s'il vous plaît fournir un algorithme polynomial qui calcule cette somme (pseudo-code ou python préféré!). Si aucun algorithme polynomial existe s'il vous plaît expliquer pourquoi.

Answer 1

Il est facile de voir que (1 + 2 + 3) * (5 + 4) * (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

Quelle est la fonction Python comme somme () mais pour la multiplication ? produit ()?

Je pense personnellement que Guido a pris une décision au sujet de mul terribles.

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