Possible categorizations using recursion

Question

I have two arrays, one contains top-level categories and another contains sub-categories where the length of sub-categories > length of top-level categories.

I'm trying to write a recursive algorithm to give me all the possible ways I can place the sub-categories into the top-level categories. So, for example, if I have top-level categories [A,B,C] and sub-categories [W,X,Y,Z] I would get:

A->WXYZ, B->null, C->null
A->XYZ,  B->W,    C->null
A->WYZ,  B->X,    C->null
...
A->null, B->Z,    C->WXY
A->null, B->null, C->WXYZ

At first glance, I don't think this problem can be solved with a typical permutation algorithm, but I could be wrong; I'm not too good with recursion.

Thanks!

Answer 1

You don't need permutations and you don't need recursion, you just need to count. Say you have N categories and M subcategories - you need to go over all the M-digit numbers in base N.

Let's take your 3 categories, but call them 0, 1 and 2 - that is, all the digits in base-3. Now let's look at all the 4 digit numbers in base 3:

0000, 0001, 0002, 0010, 0011, 0012, ... , 2212, 2220, 2221, 2222

Each number represents an allocation of subcategories to categories, like so - the first digit is for subcategory W, the second for subcategory X, the third for subcategory Y and the last is for subcategory Z.

So, 0000 means WXYZ are in the first category (your first line in the example). 1000 is your second line, 2222 is your last line, and so on.