Input: Number of boxes (nboxes) = 4, number of non-identical items (ritems) = 3
Output: [1230, 1203, 1320, 1023, 1302, 1032, 2130, 2103, 3120, 0123, 3102, 0132, 2310, 2013, 3210, 0213, 3012, 0312, 2301, 2031, 3201, 0231, 3021, 0321]
Do you remember the permutation coefficient formula which you probably learned in high school mathematics?
How can we use the above formula to place 'r' non-identical items in 'n' boxes such that n >= r?
As you can see from the above formula, the 1st item has n choices, whether to be placed in any box. Now, after the 1st item is placed, since there are n-1 boxes empty, hence the 2nd item has n-1 choices of which box to be placed. Similarly, the 3rd item has n-3 choices and so on.
We will simulate this process until we have used all the r items. Initially, all boxes will be empty (denoted by box[i] = 0 for all i = 0 to n-1).
Let us define the faith, expectation of the recursive function and then derive a recursive relation by meeting expectation with faith.
We expect that our function will give us all the permutations of r non-identical items by placing them in n boxes. We will expect from the function that it will place the current item ci, in any one empty box.
After placing the current item ci in any one box, we will keep faith on our recursive function, that it knows how to generate the permutation of the rest of the items in the empty boxes. Hence, we will keep faith that we can place all the rest items from (ci + 1 to ti) in some boxes.
As mentioned above, for the current item ci, we will try to place it in one of the empty boxes. Hence, we will run a loop over all the boxes, checking whether the box is empty or not.
If the box is empty, then we will place the current item in the box, in the edge-pre area by doing box[i] = ci, and call for the recursive function for the next item (ci + 1).
But, please keep in mind that after returning from the recursive function in the edge-post area, we will update the box back to empty, i.e. box[i] = 0.
Now, the only thing remaining is - the BASE CASE.
We should stop if we have placed all the total number of items (ti) in some boxes. Hence, when the current item (ci) becomes greater than ti, then we will print the permutation and return.
In recursion tree:
-
The LEVELS are equivalent to ITEMS.
-
The CHOICES/EDGES are equivalent to BOXES.
-
Items are numbered from 1 to ritems.