3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Hint: You want to populate $y-1$ spaces between $x$ numbers. Can you use a recursive algorithm $\endgroup$ – orezvani Mar 17 '17 at 5:45
  • $\begingroup$ You can partition X into Y different parts and then make all different permutation of all the different way to partition for example 5 can be partitioned into 3 parts in 2 ways as 1 2 2 and 1 1 3. Now you can permute this 2 arrays and get all the combinations required. $\endgroup$ – Deep Joshi Mar 17 '17 at 8:03
  • 2
    $\begingroup$ This is a nice programming exercise, which I encourage you to work out on your own, along the lines of orezvani's hint. $\endgroup$ – Yuval Filmus Mar 17 '17 at 10:52
  • 1
    $\begingroup$ Do the numbers look familiar? This is a stars and bars problem. $\endgroup$ – Thumbnail Apr 17 '17 at 8:54
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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 ...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.