Permutation - 1

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are give a number of boxes (nboxes) and number of non-identical items (ritems).
2. You are required to place the items in those boxes and print all such configurations possible.

Items are numbered from 1 to ritems.
Note 1 -> Number of boxes is greater than number of items, hence some of the boxes may remain empty.
Note 2 -> Check out the question video and write the recursive code as it is intended without changing signature. The judge can't
force you but intends you to teach a concept.
Input Format
Input is managed for you
Output Format
Check the sample ouput and question video. 0 means empty box.
Question Video
Constraints
0 < nboxes <= 10
0 <= ritems <= nboxes
Sample Input
5
3
Sample Output
12300
12030
12003
13200
10230
10203
13020
10320
10023
13002
10302
10032
21300
21030
21003
31200
01230
01203
31020
01320
01023
31002
01302
01032
23100
20130
20103
32100
02130
02103
30120
03120
00123
30102
03102
00132
23010
20310
20013
32010
02310
02013
30210
03210
00213
30012
03012
00312
23001
20301
20031
32001
02301
02031
30201
03201
00231
30021
03021
00321


  • Editorial

    The number of ways to arrange r items in n boxes is nPr. The ith item (1 <= i <=r) will be kept at level. The options will be to place the ith item in all empty boxes one by one and call the recursive function for the next level. When the number of items will be equal to the r, print the answer and return.

    Signature -

    public static void permutations(int[] boxes, int ci, int ti)

    boxes - array to store which box stores which item

    ci - current item.

    ri - total items.

    Code -

    public static void permutations(int[] boxes, int ci, int ti) {
                                            if (ci > ti) { // ci = 1 intitially
                                                for (int i = 0; i < boxes.length; i++) {
                                                    System.out.print(boxes[i]);
                                                }
                                                System.out.println();
                                                return;
                                            }
                                            for (int i = 0; i < boxes.length; i++) {
                                                if (boxes[i] == 0) {
                                                    boxes[i] = ci;
                                                    permutations(boxes, ci + 1, ti);
                                                    boxes[i] = 0;
                                                }
                                            }
                                        }

    java false

    At each level iterate through the boxes array and check which box is empty. If it is empty, place the current item in that box in pre-order, make a recursive call and increase the current item. In post - order, empty that box so it can be used again. When the current item is more than the total item, base case is reached.

    Base Case -

    When the current item is more than the total item, it means all the items are placed, print the array and return.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name