0

Given that I have m non-empty distinct sets (labeled Z[ 1 ], Z[ 2 ], ..., Z[ m ]), I aim to compute the sum of all possible subsets where there is exactly one element from each set. The size of each subset is defined to be the product of its members. For example:

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

Z[ 2 ] = {4,5}

Z[ 3 ] = {7,8}

Should result in:

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

While this is easy to code (in any language), is this a restatement of the famous subset sum problem? If not, please provide a polynomial time algorithm that computes this sum (pseudo-code or python preferred!). If no polynomial time algorithm exists please explain why.

Vinko Vrsalovic
  • 330,807
  • 53
  • 334
  • 373
Hooked
  • 84,485
  • 43
  • 192
  • 261
  • 1
    This is homework, right? – Hamish Grubijan Jan 19 '10 at 23:24
  • polynomial in terms of m? Or the total number of elements across all Z? – recursive Jan 19 '10 at 23:24
  • @ Ipthnc - This is not a homework question but a genuine physics-based problem that I came across. Assume you have many closed non-identical systems (Z1,Z2,...) all coupled to the same reservoir (at fixed T). Now observe each system only once, with those observations what is the most probable T of the reservoir? I've restated it as a computational question in hopes that CS majors have a more insight then I do. – Hooked Jan 19 '10 at 23:29
  • @ recursive - Polynomial in terms of m, where we assume the average size of the Z_i to be bounded. – Hooked Jan 19 '10 at 23:32
  • Holy crap, observable reservoir ... my head already hurts. – Hamish Grubijan Jan 19 '10 at 23:41

2 Answers2

4

It is easy to see that (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()?

I personally think that Guido made a terrible decision regarding mul.

Community
  • 1
  • 1
Hamish Grubijan
  • 10,562
  • 23
  • 99
  • 147
  • And here I thought the problem was difficult - everything is much easier (and obvious) in hindsight! Thank you Ipthnc! – Hooked Jan 19 '10 at 23:35
  • Good answer! (I +1'ed it.) FYI: note that this sort of operation -- "I have N sets, and I want to make combinations where I have one member from each of the N sets" -- is called "taking the Cartesian product" of the sets. (The fact that you then multiply the members -- and find the "product" -- is coincidental.) – Dan H Apr 11 '12 at 12:12
  • @Dan H, so is there a more general way to solve this for other "combinations" that is as fast? Is it just a matter of plugging different operators in place of mul and sum? To be honest, I had to read your comment a couple of times since Cartesian Product also means something in sql ... obviously related, but maybe not the same. – Hamish Grubijan Apr 19 '12 at 18:10
0
>>> 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
jbochi
  • 28,816
  • 16
  • 73
  • 90
  • 1
    Naively it works, but this grows exponentially with the number of terms in both |Z_i| and m and does not answer the question. – Hooked Jan 19 '10 at 23:38