登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

银河里的星星

落在人间

 
 
 

日志

 
 

一个排列生成问题-看问题思考过程  

2009-07-26 13:22:32|  分类: 思维训练 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

问题

是这样的:每次只交换相邻的两个数 如何在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/


 

  评论这张
 
阅读(1117)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018