Сумма произведения по всем комбинациям с одним элементом из каждой группы
Вопрос
Учитывая, что у меня есть m непустых различных наборов (помеченных Z[1], Z[2],..., Z[m]), я стремлюсь вычислить сумму всех возможных подмножеств, в которых есть ровно один элемент из каждого набор.Размер каждого подмножества определяется как произведение его членов.Например:
Z[ 1 ] = {1,2,3}
Z[ 2 ] = {4,5}
Z[ 3 ] = {7,8}
Должно получиться:
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
Хотя это легко закодировать (на любом языке), является ли это повторением знаменитого проблема с суммой подмножества?Если нет, предоставьте алгоритм полиномиального времени, который вычисляет эту сумму (предпочтительно псевдокод или Python!).Если алгоритма с полиномиальным временем не существует, объясните, почему.
Решение
Легко видеть, что (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
Что такое функция Python, например sum(), кроме умножения?продукт()?
Лично я считаю, что Гвидо принял ужасное решение относительно мул.
Другие советы
>>> 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