使用递归的可能分类

Question

我有两个数组,一个包含顶级类别,另一个包含子类别,其中子类别的长度>顶级类别的长度.

我正在尝试编写一个递归算法,为我提供了将子类别放入顶级类别的所有可能方法.所以,例如,如果我有顶级类别[A,B,C]和子类别,[W,X,Y,Z]我会得到:

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

乍一看,我不认为这个问题可以通过典型的排列算法来解决,但我可能是错的; 递归时我不太好.

谢谢!

Answer 1

你不需要排列,也不需要递归,你只需要计算.假设您有N个类别和M个子类别 - 您需要查看基数N中的所有M位数字.

让我们看看你的3个类别,但称它们为0,1和2 - 即base-3中的所有数字.现在让我们看看基数3中的所有4位数字:

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

每个数字代表子类别到类别的分配,如下所示 - 第一个数字用于子类别W,第二个数字用于子类别X,第三个用于子类别Y,最后一个用于子类别Z.

因此,0000表示WXYZ属于第一类(示例中的第一行).1000是你的第二行,2222是你的最后一行,依此类推.