Algorithm to calculate the number of combinations to form 100

Question

Hi

I am struck in a tricky situation where I need to calculate the number of combinations to form 100 based on different factors.

Those are

• Number of combinations
• Multiplication factor
• distance

Sample input 1: (2-10-20)

It means

• list the valid 2 way combination to form 100.
• the distance between the combination should be less than or equal to 20.
• And all of the resultant combination must be divisible by the given multiplication factor 10

Output will be

[40,60]

[50,50]

[60,40]

here [30,70],[20,60] are invalid because the distance is above 20.

Sample Input 2: [2-5-20]

[40,60]

[45,55]

[50,50]

[55,45]

[60,40]

I would really appreciate if you guided me to the right direction.

Cheers.

Answer 1

Hi

Input: (2-10-20)

1. Divide the number by param 1

(50,50)

2 Check whether the difference rule allows this combination. If it hurts the rule, then STOP, if it allows, then add this and it's combinations to the result list

For example: abs(50-50)<20, so it is ok

3 Increase the the first value by param 2, decrease the second value by param 2

1. Go 2. point

Answer 2

If you need to divide 100 over 2 with a maximum distance of N, the lowest value in the combination is

100 / 2 - N / 2

If you need to divide 100 over 3 values with a maximum distance of N, this becomes more tricky. The average of the 3 values will be 100/3, but if one of them is much lower than this average, than the other can only be slightly bigger than this average, meaning that the minimum value is not the average minus the maximum distance divided by two, but probably

100 / 3 - 2N / 3

In general with M values, this becomes

100 / M - (M-1)N / M

Which can be simplified to

(100 - (M-1)N) / M

Similarly we can calculate the highest possible value:

(100 + (M-1)N) / M

This gives you a range for first value of your combination.

To determine the range for the second value, you have to consider the following constraints:

• the distance with the first value (should not be higher than your maximum distance)
• can we still achieve the sum (100)

The first constraint is not a problem. The second is.

Suppose that we divide 100 over 3 with a maximum distance of 30 using multiples of 10 As calculated before, the minimum value is:

(100 - (3-1)30) / 3 --> 13 --> rounded to the next multiple of 10 --> 20

The maximum value is

(100 + (3-1)30) / 3 --> 53 --> rounded to the previous multiple of 10 --> 50

So for the first value we should iterate over 20, 30, 40 and 50.

Suppose we choose 20. This leaves 80 for the other 2 values. Again we can distribute 80 over 2 values with a maximum distance of 30, this gives:

Minimum: (80 - (2-1)30) / 2 --> 25 --> rounded --> 30

Maximum: (80 + (2-1)30) / 2 --> 55 --> rounded --> 50

The second constraint is that we don't want a distance larger than 30 compared with our first value. This gives a minimum of -10 and a maximum of 50.

Now take the intersection between both domains --> 30 to 50 and for the second value iterate over 30, 40, 50.

Then repeat this for the next value.

EDIT: I added the algorithm in pseudo-code to make it clearer:

calculateRange (vector, remainingsum, nofremainingvalues, multiple, maxdistance)
{
if (remaingsum==0)
   {
   // at this moment the nofremainingvalues should be zero as well
   // found a solution
   print vector
   return;
   }

minvalueaccordingdistribution = (remainingsum-(nofremainingvalues-1)*maxdistance)/nofremaingvalues;
maxvalueaccordingdistribution = (remainingsum+(nofremainingvalues-1)*maxdistance)/nofremaingvalues;

minvalueaccordingdistance = max(values in vector) - maxdistance;
maxvalueaccordingdistance = min(values in vector) + maxdistance;

minvalue = min (minvalueaccordingdistribution, minvalueaccordingdistance);
maxvalue = max (minvalueaccordingdistribution, minvalueaccordingdistance);

for (value=minvalue;value<=maxvalue;value+=multiple)
   {
   calculaterange (vector + value, remainingsum - value, nofremainingvalues-1, multiple, maxdistance);
   }
}

main()
{
calculaterange (emptyvector, 100, 2, 20);
}

Answer 3

Why can't you use a brute force approach with few optimization? For example, say N - Number of combinations M - Multiples D - Max possible Distance

So possible values in combinations can be M, 2M, 3M and so on. You need to generate this set and then start with first element from set and try to find out next two from choosing values from same set (provided that they should be less than D from first/second value). So with i/p of 3-10-30 would

1. Create a set of 10, 20, 30, 40, 50, 60, 70, 80, 90 as a possible values
2. Start with 10, choice for second value has to be 20, 30, 40, 50 (D < 30)
3. Now choose second value from set of 20, 30, 40, 50 and try to get next value and so on

If you use a recursion then solution would become even simpler.

1. You have to find N values from a list of possible values within MIN & MAX index.
2. So try first value at MIN index (to MAX index). Say we have chosen value at X index.
3. For every first value, try to find out N-1 values from the list where MIN = X + 1 and MAX.

Worst performance will happen when M = 1 and N is sufficiently large.

Answer 4

Is the distance between all the additive factors, or between each of them? For example, with 3-10-20, is [20-40-60] a valid answer? I'll assume the latter, but the solution below can be modified pretty trivially to work for the former.

Anyway, the way to go is to start with the most extreme answer (of one sort) that you can manage, and then walk the answers along until you get to the other most extreme.

Let's try to place numbers as low as possible except for the last one, which will be as high as possible (given that the others are low). Let the common divisor be d and divide 100 by it, so we have S = 100/d. This quantizes our problem nicely. Now we have our constraint that spacing is at most s, except we will convert that to a number of quantized steps, n = s/d. Now assume we have M samples, i1...iM and write the constraints:

i1 + i2 + i3 + ... + iM = S
0 <= i1 <= n
0 <= i2 <= n
. . .
0 <= iM <= n
i1 <= i2
i2 <= i3
. . .
i(M-1) <= iM

We can solve the first equation to get iM given the others.

Now, if we make everything as similar as possible:

i1 = i2 = ... = iM = I
M*I = S
I = S/M

Very good--we've got our starting point! (If I is a fraction, make the first few I and the remainder I+1.) Now we just try to walk each variable down in turn:

for (i1 = I-1 by -1 until criteria fails)
  sum needs to add to S-i1
  i2 >= i1
  i2 <= i1 +n
  solve the same problem for M-1 numbers adding to S-i1
  (while obeying the above constraint on i2)

Well, look here--we've got a recursive algorithm! We just walk through and read off the answers.

Of course, we could walk i1 up instead of down. If you need to print off the answers, may as well do that. If you just need to count them, note that counting up is symmetric, so just double the answer you get from counting down. (You'll also have a correction factor if not all values started the same--if some were I and some were I+1, you need to take that into account, which I won't do here.)

---

Edit: If the range is what every value has to fit within, instead of all the

0 <= i1 <= n

conditions, you have

max(i1,i2,...,iM) - min(i1,i2,...,iM) <= n

But this gives the same recursive condition, except that we pass along the max and min of those items we've already selected to throw into the mix, instead of adding a constraint on i2 (or whichever other variable's turn it is).

Answer 5

I hope it's not a homework problem!

    def combinations(n: Int, step: Int, distance: Int, sum: Int = 100): List[List[Int]] =
      if (n == 1) 
        List(List(sum))
      else 
        for {
          first <- (step until sum by step).toList
          rest <- combinations(n - 1, step, distance, sum - first)
          if rest forall (x => (first - x).abs <= distance)
        } yield first :: rest