排列组合序列的递归生成.docxVIP

排列组合序列的递归生成在进行数学计算或者图论等问题解答时，很有可能会遇到组合序列生成问题，此类问题如果不仔细分析，很难摸到门道，这里做个简单介绍。先看两个问题：问题1输入一个非负最大值序列，例如 [2,3]，生成其可能取值情况？其中2，3，分别表示该层的最大取值，求其全部可能情况。意思就是说生成的结果应该是两位，第一位不能超过2，第二位不能超过3，则所有可能情况有：[00, 01, 02, 03, 10, 11, 12, 13, 20, 21, 22, 23]问题2任意正整数可以有唯一分解式其中 p1 p2 为质数，请问在已知序列P和A的情况下，如何求得N的全部因子？例如可以由底数序列 [2 3]和指数序列 [2 2]来联合表示，如何利用这两个序列求得36的全部因子[1, 2, 3, 4, 6, 9, 12, 18, 36]？对于问题1，一个很大的应用场合就是对于嵌套循环层次非常多的代码可以非常有效的简化代码。我们来分析一下问题的思考过程：对于问题1，如果采用普通循环方法来做，那么我们输入的序列有多少个元素，则会产生多少重嵌套的循环。对于长度不确定的输入，我们很难预先构造好循环代码。所以我们考虑采用递归思路来解决这个问题。首先我们形成递归思考的意识，递归的过程实际就是把问题分解成子问题的过程，而子问题又与原始问题有极大的相似性。比如假定我们有处理序列 [a b c]的递归函数fx，则我们可以考虑先处理a，然后利用fx来处理剩下的 [b c]，而序列 [a b c]和 [b c]除了长度不一致，处理起来没有本质的区别。然后我们注意考虑一下递归的终止条件，就ok了。具体分析一下问题1：我们先判断出，问题1的解的规模会随着输入数据的增大而迅速增大，所以我们在递归函数内部要考虑如何对我们的输出数据进行扩充。我们再分析一下终止条件，对于最简单的输入（只有一个元素的列表），我们需要返回的应该是0到该数的一个列表。所以根据以上的分析，我们基本可以开始构建程序了，下面是一段python写的代码：上述代码中，我们可以看到if语句实际上就是终止代码，ret用于存放我们的结果，每一个元素都是一个字符串，递归函数算法为总的结果为该问题的子问题的全部结果每一个都加上我们第一个元素循环构成。讲的不太清楚，大家根据代码仔细揣摩其本质。对于问题2，实际上就是问题1的升级版，本质上是将指数序列进行问题1的构造，然后用底数序列与构造生成的新序列计算得到全部因子。代码如下：大家可以观察一下如何在问题1的基础上加上计算来生成新的结果。结束语：递归函数的使用比较有技巧性，很考验大家对问题的理解深度，可以多加练习。代码只是实验代码，为考虑异常等问题，不喜勿喷。希望对大家有启发。Winxos 2012-06-24附完整代码(python 2.7 下编译通过)： test.py# -*- coding: cp936 -*-#组合问题递归算法#winxos 2012-06-23#组合数字递归序列生成#输入n为整数列表,例如输入[1,2]#则输出[00, 01, 02, 10, 11, 12]def combination(n):iflen(n)==1:return range(0,n[0]+1) ret=[] #存放组合结果fori in range(0,n[0]+1):for li in combination(n[1:]):ret.append(str(i)+str(li))return ret#由整数质因子及其数目求该整数的全部因子#例如 36=2^2 x 3^2#本质上是根据指数[2 2]的全部可能序列与底数运算得到def factors(c,n):iflen(n)==1:ret=[]fori in range(0,n[0]+1):ret.append(c[0]**i)return ret ret=[] #每次迭代，将会扩充列表 for i in range(0,n[0]+1): #求c^a次方，a为0-n范围内的整数for li in factors(c[1:],n[1:]):ret.append(c[0]**i*li) #扩充列表大小ret.sort()return ret#main testprint combination([2,1,4,1])print factors([2,3,5],[2,1,3])执行结果[0000, 0001, 0010, 0011, 0020, 0021, 0030, 0031, 0040, 0041, 0100, 0101, 0110, 0111, 0120, 0121, 0130, 0131, 0140, 0141, 1000, 1001, 1010, 1011, 1020, 1021, 1030, 1031,