rambo

划分相关题目(转载)

问题1:整数划分问题是将一个正整数n拆成一组数连加并等于n的形式,且这组数中的最大加数不大于n。

共11种。下面介绍一种通过递归方法得到一个正整数的划分数。

递归函数的声明为 int split(int n, int m);其中n为要划分的正整数,m是划分中的最大加数(当m > n时,最大加数为n),
1 )当n = 1或m = 1时,split的值为1,可根据上例看出,只有一个划分1 或 1 + 1 + 1 + 1 + 1 + 1
可用程序表示为if(n == 1 || m == 1) return 1;

2 )下面看一看m 和 n的关系。它们有三种关系
(1) m > n
在整数划分中实际上最大加数不能大于n,因此在这种情况可以等价为split(n, n);
可用程序表示为if(m > n) return split(n, n);
(2) m = n
这种情况可用递归表示为split(n, m - 1) + 1,从以上例子中可以看出,就是最大加
数为6和小于6的划分之和
用程序表示为if(m == n) return (split(n, m - 1) + 1);
(3) m < n
这是最一般的情况,在划分的大多数时都是这种情况。
从上例可以看出,设m = 4,那split(6, 4)的值是最大加数小于4划分数和整数2的划分数的和。
因此,split(n, m)可表示为split(n, m - 1) + split(n - m, m)

问题2:令E=\{e_{1}, ...,e_{n}\}表示n 个元素的集合,我们的目标是生成该集合的所有排列方式。

递归版本:E_{i} 为E中移去元素i 以后所获得的集合,perm (X) 表示集合X 中元素的排列方式,e_{i}.perm(X)表示在perm (X)中的每个排列方式的前面均加上e_{i}以后所得到的排列方式。例如,如果E= \{a,b,c\},那么E_{1}= \{b,c\}perm (E_{1}) = (bc,cb)e_{1}.perm (E_{1}) = (a b c, a c b)

对于递归的基本部分,

  • 采用n = 1。当只有一个元素时,只可能产生一种排列方式,所以perm (E) = (e),其中e 是E 中的唯一元素。
  • 当n > 1时,perm (E) = e_{1}.perm (E_{1}) +e_{2}.perm(E_{2}) +e_{3}.perm (E_{3})+...+e_{n}.perm (E_{n})。这种递归定义形式是采用n 个perm (X) 来定义perm (E), 其中每个X 包含n- 1个元素。至此,一个完整的递归定义所需要的基本部分和递归部分都已完成。
  • 当n= 3并且E=(a, b, c)时,按照前面的递归定义可得perm (E) =a.perm (\{b,c\})+b.perm(\{a,c\})+c.perm(\{a,b\})。同样,按照递归定义有perm(\{b,c\})=b.perm (\{c\}) +c.perm(\{b\}), 所以a.perm(\{b,c\}) = ab.perm(\{c\}) + ac.perm(\{b\})=ab.c +ac.b =(a b c, a c b)。同理可得b.perm(\{a,c\}) =ba.perm(\{c\})+bc.perm(\{a\}) =b a . c + b c . a = (b a c, b c a)c.perm(\{a, b\}) =ca.perm (\{b\}) + cb.perm (\{a\}) = c a . b + c b . a = (c a b, c b a)。所以perm (E) = (a b c, a c b, b a c, b c a,c a b, c b a)。注意a.perm ( \{b, c\})实际上包含两个排列方式:abc 和acb,a是它们的前缀,perm (\{b, c\})是它们的后缀。同样地,ac.perm ( {b}) 表示前缀为a c、后缀为perm ( {b}) 的排列方式。

输出所有前缀为list [0:k-1], 后缀为list[k:m] 的排列方式。调用Perm(list, 0, n-1) 将得到list[0: n-1] 的所有n! 个排列方式,在该调用中,k=0, m= n - 1,因此排列方式的前缀为空,后缀为list[0: n-1] 产生的所有排列方式。当k =m 时,仅有一个后缀l i s t [ m ],因此list[0: m] 即是所要产生的输出。当k<m时,先用list[k] 与list [k:m] 中的每个元素进行交换,然后产生list[k+1: m] 的所有排列方式,并用它作为list[0: k] 的后缀

设数组a[] ={"A","B","C","D"}

fab3ac119313b07eef0244390ed7912397dd8c00

QQ截图20150913001000

思想:

  1. 用数组记录操作后的序列,输出结果时只需要输出该数组即可;
  2. 交换第1个元素与第i(1=<i<=n)个元素,得到n个序列;把每个序列分成两部分:第一个元素,其余的元素;对其余元素执行全排列操作;(记得操作完后,将这两个元素交换回来,以方便下面的交换)
  3. 当剩余序列中只有一个元素时,得到一种排列结果,输出该结果

逻辑方法不变:每一层都是排列
规模不断变小:排完第一个位置后排后面(n-1) 个位置,依次递推。
终止条件:排到最后一个的时候(本次采用的是交换方法所以只需排到n-1就行了)

思考:

  • 该算法怎么不是按顺序排列?因为算法本身特点,只是在大框架下保证顺序输出【记以1开头的6个,接着是以2开头的,接着以3开头的序列(首个为3214),……】;由于1234因调换<1-3>就出现了3214且以其作为3序列的开头,而3124比它小,却只能排在它后面。
  • 如果数组有重复怎么办?,例:求“1223”的全部排列?

非递归版本:我们先来研究一下STL中的源码。

首先,从最尾端开始往前寻找两个相邻元素,令第一元素为*i,第二元素为*ii,且满足*i<*ii。找到这样一组相邻元素后,再从最尾端开始往前检验,找出第一个大于*i的元素,令为*j,将i,j对调,再将ii之后的所有元素颠倒排列。

QQ截图20150913004155

QQ截图20150913004143

根据标记从后往前比较相邻两数据,若前者小于(默认为小于)后者,标志前者为X1(位置PX)表示将被替换,再次重后往前搜索第一个不小于X1的数据,标记为X2。交换X1,X2,然后把[PX+1,last)标记范围置逆。完成。

为什么这样就可以保证得到的为最小递增?

从位置first开始原数列与新数列不同的数据位置是PX,并且新数据为X2。[PX+1,last)总是递减的,[first,PX)没有改变,因为X2>X1,所以不管X2后面怎样排列都比原数列大,反转[PX+1,last)使此子数列(递增)为最小。从而保证的新数列为原数列的字典序排列next。

明白了这个原理后,看下面例子:

因为原数列不是从最小字典排列开始。所以"如果要走遍所有的排列,你必须先将元素排序"。

参考资料:

1)http://blog.csdn.net/morewindows/article/details/7370155/

2)《STL源码剖析》

3)http://www.cnblogs.com/caixu/archive/2011/10/31/2229862.html

4)http://acm.hdu.edu.cn/showproblem.php?pid=1027