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

Учитывая, что у меня есть 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!). Если алгоритм полиномиального времени не существует, объясните, почему.


algorithm subset
person Hooked    schedule 19.01.2010    source источник
comment
Это домашнее задание, да?   -  person Hamish Grubijan    schedule 20.01.2010
comment
многочлен по m? Или общее количество элементов по всему Z?   -  person recursive    schedule 20.01.2010
comment
@ Ipthnc - Это не вопрос домашнего задания, а настоящая проблема, основанная на физике, с которой я столкнулся. Предположим, у вас есть много замкнутых неидентичных систем (Z1,Z2,...), связанных с одним и тем же резервуаром (при фиксированном T). Теперь наблюдайте за каждой системой только один раз, при этих наблюдениях какова наиболее вероятная Т резервуара? Я переформулировал это как вычислительный вопрос в надежде, что у специалистов по CS будет больше понимания, чем у меня.   -  person Hooked    schedule 20.01.2010
comment
@ рекурсивный — полиномиальный по m, где мы предполагаем, что средний размер Z_i ограничен.   -  person Hooked    schedule 20.01.2010
comment
Святое дерьмо, обозримое водохранилище... аж голова болит.   -  person Hamish Grubijan    schedule 20.01.2010

Ответы (2)


arrow_upward
4
arrow_downward

Легко видеть, что (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(), но для умножения? продукт()?

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

person Hamish Grubijan    schedule 19.01.2010
comment
А тут я думал проблема сложная - задним числом все гораздо проще (и очевидно)! Спасибо Iptnc! - person Hooked; 20.01.2010
comment
Хороший ответ! (Я поставил +1.) К вашему сведению: обратите внимание, что такого рода операция — у меня есть N наборов, и я хочу создать комбинации, в которых у меня есть один элемент из каждого из N наборов — называется декартовым произведением наборы. (Тот факт, что вы затем умножаете члены и находите произведение, является случайным.) - person Dan H; 11.04.2012
comment
@Dan H, так есть ли более общий способ решить эту проблему для других комбинаций, который будет таким же быстрым? Это просто вопрос подключения разных операторов вместо mul и sum? Честно говоря, мне пришлось пару раз прочитать ваш комментарий, так как декартово произведение тоже означает что-то в sql... очевидно, связанное, но, возможно, не одно и то же. - person Hamish Grubijan; 19.04.2012

arrow_upward

arrow_downward

person    schedule
comment
Наивно это работает, но это растет экспоненциально с количеством терминов в обоих |Z_i| и м и не отвечает на вопрос. - person Hooked; 20.01.2010