Сумма продукта по всем комбинациям с одним элементом из каждой группы

Учитывая, что у меня есть 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

Хотя это легко кода (на любом языке), является ли это пересчет знаменитых subset sum problem? Если нет, укажите алгоритм полиномиального времени, который вычисляет эту сумму (предпочтительный псевдокод или питон!). Если алгоритм полиномиального времени не существует, объясните, почему.

источник

2010-01-19 Hooked

Это домашнее задание, не так ли? –

полином в терминах m? Или общее количество элементов во всех Z? – recursive

@ Ipthnc - Это не вопрос домашней работы, а настоящая физическая проблема, с которой я столкнулся. Предположим, что у вас много замкнутых неидентичных систем (Z1, Z2, ...), связанных с одним и тем же резервуаром (при фиксированном T). Теперь наблюдайте каждую систему только один раз, с этими наблюдениями, что является наиболее вероятным T резервуара? Я переформулировал это как вычислительный вопрос в надежде, что у майоров CS будет больше понимания, чем я. – Hooked

Легко видеть, что (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()?

Я лично считаю, что Гвидо сделал ужасное решение относительно мула.

источник

2010-01-19 23:25:27

И здесь я думал, что проблема была сложная - все гораздо проще (и очевидно) в ретроспективе! Спасибо, Ipthnc! – Hooked

Без проблем :) 15 char –

Хороший ответ! (I + 1). FYI: обратите внимание, что такая операция - «У меня есть N наборов, и я хочу создавать комбинации, где у меня есть один член из каждого из N наборов» - называется «принимая Декартово произведение "множеств. (То, что вы затем умножаете членов - и находите «продукт» - совпадение.) –

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

источник

2010-01-19 23:27:56 jbochi

Наивно это работает, но это растет экспоненциально с количеством членов как в | Z_i | и m и не отвечает на вопрос. – Hooked

Сумма продукта по всем комбинациям с одним элементом из каждой группы

ответ

Смежные вопросы