Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sum of all possible products when each product has a maximum

  1. Nov 29, 2013 #1

    I have a set of sets of real numbers greater than 1. Each set can have a different quantity of numbers.
    Set A1 {a11, a12,...a1m1}
    Set A2 {a21, a22, ..., a2m2}
    Set AN {aN1, aN2, ..., aNmN}

    If I want the sum of all possible products that have one element from each set, that's easy: (a11+a12+...+a1m1)x(a21+a22+...+a2m2)x...x(aN1+aN2+...+aNmN).
    But what i interested in is the sum of all possible products that have one element from each set BUT if the product is Higher than K, then the product must be included as K, not as its real value.
    Short example:
    Set A1 (2,3)
    Set A2 (7,9)
    K = 20
    Usual sum = 14 + 21 + 18 + 27
    Sum I am interested in: 14 + 20 + 18 + 20

    What's the fastest way to calculate it? is it possible to do this with a neat formula or am I forced to cycle over all combinations?

  2. jcsd
  3. Nov 29, 2013 #2


    User Avatar
    2017 Award

    Staff: Mentor

    I don't see how to calculate this without any loops. You don't have to consider all combinations - as an example, if a1*a2*a3 > K and you have 10 sets, you can calculate m4*m5*...*m10 combinations at once as they all give K.
    On the other hand, if a1*a2*a3 * (maximal element of A4) * ... < K, you can ignore the limit and calculate all sums as well. Starting the loops with a clever choice of sets could save some time, but that depends on the numbers.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook