Stuck on a combinations algo question

Question

There are x digits and y boxes where y is between 1 and x inclusive. I have to print all the possible digits in boxes (combinations) in any order.

For examples, if x = 5 and y = 2 we can have the following 4 combinations:

1234 5
123 45
12 345
1 2345

Similarly if x = 5 and y = 3

123 4 5
12 34 5
12 3 45
1 234 5
1 23 45
1 2 345

if x = 5 and y = 5 then there is only 1 combination

1 2 3 4 5

Both x and y are variable and I can't figure out even a brute force way of doing this. I have tried using three nested for loops but have no luck.

Answer 1

You can print numbers 1 to $x$ and print $y-1$ spaces between them in a brute force manner. The following algorithm does that:

function enumerate(string str, int s, int t, int y):
   /* base case: there is no space left and we print the string */
   if (y==0)
      string str2 = "";
      for i=s to t:
         str2.append(i);
       print str+str2;
       return ;

   /* recursive case: add one space and recursively call the function */
   for i=s to t:
      string str2 = "";
      for j=s to i-1:
         str2.append(j);
      str2.append("~");
      if (t-i >= y-1) call enumerate(str+str2, i, t, y-1);

You can call enumerate(str="", s=1, t=5, y=2) to print all combinations of numbers 1 to 5 and 2 spaces between them, which gives you a sorted embedding of numbers 1 to 5 in 3 boxes.

Answer 2

Expanding on orezvani's hint:

If you have x balls and y boxes, how many balls can you put in the first box?

• If there is only one box, you have to put all the balls in it.
• Otherwise, you must leave at least y - 1 to be able to put one in each of the other boxes.

However many you choose, you will be left with a similar problem. Cue recursive function ...