algorithm - 动态规划求解置换

Question

我有四个数字，“1”、“2”、“3”、“4”。

程序的输入是一个只能由以上4位数字组成的整数。将会有很多输入。

输入示例:1123、4123、4444

我需要计算符合以下规则的给定输入的排列数:

1. 任何两个相似的数字都不应相邻。示例:不允许使用 1223，但允许使用 2123。
2. 开始结束结束的数字不能相同。它们被认为是循环相邻的。示例:不允许使用 2132。
3. 如果输入的长度为 4 位数字，则生成的排列长度也应为 4 位数字。

我可以使用任何类型的内存来解决这个问题吗？我如何将它存储在二维数组中？请提供提示谢谢!

Answer 1

由于您只对允许排列的数量感兴趣，因此大多数输入都会产生相同的结果。

• 输入中数字的顺序无关紧要
• 只有数字的频率分布很重要，即 1123 和 1223 导致相同的答案。

根据数字频率对输入进行分类导致四位输入只有 5 种不同的情况:

class     examples
4         4444, 2222, ...
3 1       1211, 2232, ...
2 2       1331, 4422, ...
2 1 1     3413, 1123, ...
1 1 1 1   1234, 4231, ...

一旦您找出每个案例的答案，任何新的输入都可以非常快速地处理。