求数字组合的7种实用方法

【出自HW面试题】

难度系数：★★★★☆ 被考察系数：★★★★☆

题目描述：

用1、2、2、3、4和5这六个数字，写一个main函数，打印出所有不同的排列，例如：512234、412345等，要求：“4”不能在第三位，“3”与“5”不能相连。

分析与解答：

打印数字的排列组合方式的最简单的方法就是递归，但本题存在两个难点：第一，数字中存在重复数字，第二，明确规定了某些位的特性。显然，采用常规的求解方法似乎不能完全适用了。

其实，可以换一种思维，把求解这6个数字的排列组合问题转换为大家都熟悉的图的遍历的问题，解答起来就容易多了。可以把1、2、2、3、4和5这6个数看成是图的6个结点，对这6个结点两两相连可以组成一个无向连通图，这6个数对应的全排列等价于从这个图中各个结点出发深度优先遍历这个图中所有可能路径所组成的数字集合。例如，从结点“1”出发所有的遍历路径组成了以“1”开头的所有数字的组合。由于“3”与“5”不能相连，因此，在构造图的时候使图中“3”和“5”对应的结点不连通就可以满足这个条件。对于“4”不能在第三位，可以在遍历结束后判断是否满足这个条件。(www.xing528.com)

具体而言，实现步骤如下所示：

（1）用1、2、2、3、4和5这6个数作为6个结点，构造一个无向连通图。除了“3”与“5”不连通外，其他的所有结点都两两相连。

（2）分别从这6个结点出发对图做深度优先遍历。每次遍历完所有结点的时候，把遍历的路径对应数字的组合记录下来，如果这个数字的第三位不是“4”，则把这个数字存放到集合Set中（由于这6个数中有重复的数，因此，最终的组合肯定也会有重复的。由于集合Set的特点为集合中的元素是唯一的，不能有重复的元素，因此，通过把组合的结果放到Set中可以过滤掉重复的组合）。

（3）遍历Set集合，打印出集合中所有的结果，这些结果就是本问题的答案。实现代码如下：

由于结果过多，因此这里就不列出详细的运行结果了。