Summe des Produkts über alle Kombinationen mit einem Element aus jeder Gruppe

Question

Da ich m nicht leer verschiedene Sätze (mit der Bezeichnung Z [1], Z [2], ..., Z [m]) habe, versuche ich die Summe aller möglichen Teilmengen zu berechnen, wo es genau ist eine Element aus jedem Satz. Die Größe der einzelnen Teilmenge ist definiert als das Produkt seiner Mitglieder zu sein. Zum Beispiel:

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

Z[ 2 ] = {4,5}

Z[ 3 ] = {7,8}

Sollte in Folge:

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

Während dies leicht zu Code ist (in jeder Sprache), ist dies eine Neuformulierung der berühmten Teilmenge Summe Problem ? Wenn nicht, bitte eine Polynomialzeitalgorithmus, der diese Summe berechnet (Pseudo-Code oder Python bevorzugt!). Wenn kein Polynomialzeitalgorithmus existiert bitte erklären, warum.

Answer 1

Es ist leicht zu sehen, dass (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

Was ist die Python-Funktion wie sum () aber für die Multiplikation ? Produkt ()?

Ich persönlich denke, dass Guido eine schreckliche Entscheidung über mul gemacht.

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