Algorithm to calculate the number of combinations to form 100

Question

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

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

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);
}