问题
是这样的：每次只交换相邻的两个数 如何在n!次交换中找到所有的排列。
问题可能有些问题，n!-1次交换更合适，当然说n！也可以，但是不要把第一个开始元素算在呢。看到这个问题时大概想到了两个思路，一个根据排列之间的相邻关系，组成一个图，证明这个图中存在一个汉密尔顿路。另一个则是采用递归的思路，首先我假设可以利用相邻交换求出n-1个元素的全排列，然后看怎样利用这n-1，求出n个元素的全排列。
当然可能还可以联想到其他方面，比如格雷码，具有类似的特征，它是只有一位不同。或者我们不急着找到这样一个方案，首先证明这个方案是存在的。当然如果找到了这样一个方案也就不用证明存在了，而且很多证明都是通过构造出一个方案来证明存在性。
汉密尔顿回路
在考察汉密尔顿回路时，发现它的特殊情况对度数的要求都很大。比如Dirac 定理：设一个无向图中有 N 个节点，若所有节点的度数都大于等于 N/2，则汉密尔顿回路一定存在。但是可以看到全排列中顶点的数目是n!,但是每个点的度数只有n-1，这个差距太大，根本找不到相似性。所以要先把这个思路放下。
递归
然后在看能否利用递归。当时是这样想的：如果我的n-1元素可以做好，那如果我进行n次的n-1个元素的排列就可以完成n个元素的排列了。这样我只要每次重排时交换一个元素就可以了，比如每次我都让一个新元素位于头部，然后尾部的n-1个元素，再进行生成。这样如果每次n-1个元素的排列能让一个新元素排到第一个位置，就可以让所有的元素有机会跑到第一个位置。所以对n-1个元素，做了一个更严格的假设，假设它们经过(n-1)!次交换后，不仅可以找到所有的排列，还可以让整个排列循环左移一位。比如12345->可以变成23451.这样我们可以处理5个元素时，可以先让后4个元素排列一遍，比如1 2345 -> 1 3452，下面在交换1 3，可以进行3 1452如此进行下去，就可以让所有的元素有机会来到第一个位置。但是这个思路，却无法保证n个元素也能够保持这种循环左移一位的性质，这样归纳就进行不下去了。
实际上整个递归的思路是对的，就是我们可以利用n-1个元素的排列生成方案，完成n个元素的排列生成。
格雷码的设计
在此之前，我们先看另一个问题，如何生成相邻数只有一位不同的编码，也就是n位的格雷码应该怎么排列，才能保证相邻的是只有一位不同？
实际上格雷码的设计，也具有递归的思路。比如我们假设现在已经有了n-1位的格雷码，怎么生成n位的格雷码呢？很简单，我们可以看到n位和n-1位的区别只有一位，也就是把n-1位全部补上0，全部不上1就是n位的那些数字了。这样我们首先全部补0，这些补0的保持原来的顺序，显然它们相邻的依然只有一位不同。那么如果把补1的再衔接到补0的那些后面呢？我们只要把原来的顺序颠倒一下，就可以了，也就是让最后补0的和第一个补1的是同一个就可以保证，它们不同的位只有一位了。如下所述：
0*****
0#####
1#####
1*****
只要这样搞，就能根据n-1位的，生成n位的了。而对于1位的排列，就是0 1,通过这个基础，结合数学归纳法也可以直接证明。
邻位对换法
对于全排列的生成，也可以利用类似的思路。首先假设我们已经可以通过邻位对换生成n-1个元素的全排列。那么如果加入一个新元素，我们还缺少那些排列呢？
实际上可以看到，加入一个新元素，实际上只要把这个新元素在原n-1个元素的全排列中所有可能的位置罗列一遍，实际上就是新的全排列。比如如果原排列是123，假设新元素4，那么它对应的新的排列就是4123，1423，1243，1234,可以看到它们之间刚好都可以通过对换完成。
这样我们只要把所有的n-1个元素的排列罗列出来，然后让第n个元素，在它们之间走一遍就可以了。这样我们没次罗列一个n-1元素的排列，就让新元素走一遍，然后让新元素跑到排列的首或者尾部，然后再进行n-1个元素的下一步对换，从而到达下一个n-1元素的排列，然后再让新元素走一遍，如此往复，就完成了n个元素的全排列的生成。而且可以看到全部的操作都是通过邻位的对换完成的。
可以见只要有了n-1个元素的生成方法，就可以得到n个元素的生成方法。而2个元素的生成方法可以得到，就是12->21，由2得3，由3得4，如此归纳下去，可到无穷。
实际上这个就是全排列的一个生成方法：邻位对换法。在一般的组合数学书都有介绍。但如果真要让自己去想，还是要经过一番思考的。
转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/70971767200962612232282/
评论