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, ...

一旦找到每种情况的答案，任何新输入都可以非常快速地处理。