Java递增序列排列算法：排除重复解决公司笔试题

在Java编程领域，遇到这样一个著名的软件公司在笔试中的算法题：使用数字1、2、2、3、4、5，编写一个`main`函数，生成所有不同的递增排列，但需满足特定条件：数字"4"不能在第三位，同时"3"和"5"不能相邻。由于题目强调了避免重复，所以解决方法涉及到递归和排除重复的逻辑。 首先，我们需要明确的是，递归是解决这个问题的关键策略。递归的过程是从最长的序列（即6个数字）开始，逐个尝试改变尾部的两个数字，例如将45变成54，然后再扩展到剩余的数字。对于每个新的组合，我们需要检查它是否符合要求，即是否是递增的且不违反"4"的位置和"3"、"5"的相邻规则。 在实现上，可以定义一个`test`类，包含以下几个重要属性： 1. `CurFixPart`：当前固定的数字部分，用于存储已确定的递增序列。 2. `PreGenNum`：上一个生成的数字序列，用于后续的比较以避免重复。 `main`函数首先实例化一个`test`对象，并调用`GenControll`方法，传入初始序列"122345"。 `shift`方法的作用是将字符串`s`中的指定位置`pos`的字符移动到最前面，如果字符串长度小于等于`pos+1`，则简单处理；否则，按照子串拼接顺序操作。 `validate`方法是核心逻辑，它接受一个新生成的数字序列`newNum`，并将其与`CurFixPart`拼接形成`newGenNum`。接着，它检查： - `newGenNum`是否小于等于`PreGenNum`，如果是，则返回0，表示不符合递增要求。 - 检查`newGenNum`的第3位是否是"4"，如果满足条件，则返回0。 - 检查`newGenNum`是否包含"35"或"53"，如果存在则返回0，防止"3"和"5"相邻。 如果以上条件都不满足，说明这个序列是有效的，更新`PreGenNum`为当前的`newGenNum`，并将其打印出来。最后返回0表示继续递归。 `GenControll`方法则是整个过程的驱动者，通过递归调用自身来生成所有可能的序列，每次调用时改变尾部的两个数字，直到生成所有符合条件的递增排列。 这个算法虽然使用了递归，但由于对每个新生成的序列进行验证，有效地减少了重复计算，提高了效率。通过这种方法，我们可以生成所有满足条件的不同递增排列，比如512234、412345等。