algorithm - 使用递归的可能分类

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 - 即以 3 为基数的所有数字。现在让我们看看以 3 为基数的所有 4 位数字:

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

每个数字代表子类别到类别的分配，就像这样 - 第一个数字代表子类别 W，第二个数字代表子类别 X，第三个数字代表子类别 Y，最后一个数字代表子类别 Z。

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