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

Question

Étant donné que j'ai m ensembles distincts non vides (étiquetés Z [1], Z [2], ..., Z [m]), je vise pour calculer la somme de tous les sous-ensembles possibles où il y a exactement un élément de chaque ensemble. La taille de chaque sous-ensemble est définie comme étant le produit de ses membres. Par exemple:

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

Z[ 2 ] = {4,5}

Z[ 3 ] = {7,8}

devrait se traduire par:

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 retraitement du fameux subset sum problem? Sinon, veuillez fournir un algorithme de temps polynomial qui calcule cette somme (pseudo-code ou python préféré!). S'il n'existe pas d'algorithme de temps polynomial, veuillez expliquer pourquoi.

Answer 1

Il est facile de voir 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 

What's the Python function like sum() but for multiplication? product()?

Je pense personnellement que Guido a fait une décision terrible concernant 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