全排列生成算法
全排列的生成算法对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。字典序法按照字典序求下一个排列的算法 /*例字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。注意一个全排列可看做一个字符串，字符串可有前缀、后缀。*/生成给定全排列的下一个排列所谓一个全排列的下一个排列就是这一个排列与下一个排列之间没有其他的排列。这就要求这一个排列与下一个排列有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。/*例 839647521是1—9的排列。1—9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。算法: 由P1P2…Pn 生成的下一个排列的算法如下:1. 求i=max{j| Pj-1 全排列的生成算法 2008年04月25日星期五下午03:23 全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。任何n个字符集的排列都可以与1～n的n个数字的排列一一对应，因此在此就以n个数字的排列为例说明排列的生成法。 n个字符的全体排列之间存在一个确定的线性顺序关系。所有的排列中除最后一个排列外，都有一个后继；除第一个排列外，都有一个前驱。每个排列的后继都可以从它的前驱经过最少的变化而得到，全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法。 全排列的生成法通常有以下几种： 字典序法 递增进位数制法 递减进位数制法 邻位交换法 n进位制法 递归类算法 1.字典序法 字典序法中，对于数字1、2、3......n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是54321。 字典序算法如下： 设P是1～n的一个全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn 1）从排列的右端开始，找出第一个比右边数字小的数字的序号j（j从左端开始计算），即j=max{i|pi 3）对换pi，pk 4）再将pj+1......pk-1pkpk+1pn倒转得到排列p'=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，这就是排列p的下一个下一个排列。 例如839647521是数字1～9的一个排列。从它生成下一个排列的步骤如下： 自右至左找出排列中第一个比右边数字小的数字4 839647521 在该数字后的数字中找出比4大的数中最小的一个5 839647521 将5与4交换839657421 将7421倒转839651247 所以839647521的下一个排列是839651247。 程序代码如下： Private Sub Dict(p() As Integer, ByVal n As Integer) Dim i As Integer, j As Integer OutL p i = n - 1 Do While i > 0 If p(i) < p(i + 1) Then For j = n To i + 1 Step -1 '从排列右端开始 If p(i) <= p(j) Then Exit For '找出递减子序列 Next Swap p(i), p(j) '将递减子序列前的数字与序列中比它大的第一个数交换 For j = n To 1 Step -1 '将这部分排列倒转 i = i + 1 If i >= j Then Exit For Swap p(i), p(j) Next OutL p '输出一个排列 i = n End If i = i - 1 Loop End Sub Swap p(i), p(j)是交换两个元素的子过程，OutL p是输出排列的子过程。 2.递增进位数制法 在递增进位制数法中，从一个排列求另一个排列需要用到中介数。如果用ki表示排列p1p2...pi...pn中元素pi的右边比pi小的数的个数，则排列的中介数就是对应的排列k1 ...... ki...... kn-1。 例如排列839647521的中介数是72642321，7、2、6、......分别是排列中数字8、3、9、......的右边比它小的数字个数。 中介数是计算排列的中间环节。已知一个排列，要求下一个排列，首先确定其中介数，一个排列的后继，其中介数是原排列中介数加1，需要注意的是，如果中介数的末位kn-1+1=2，则要向前进位，一般情形，如果ki+1=n-i+1，则要进位，这就是所谓的递增进位制。例如排列839647521的中介数是72642321，则下一个排列的中介数是67342221+1=67342300（因为1+1=2，所以向前进位，2+1=3，又发生进位，所以下一个中介数是67342300）。 得到中介数后，可根据它还原对应得排列。算法如下： 中介数k1、k2、......、kn-1的各位数字顺序表示排列中的数字n、n-1、......、2在排列中距右端的的空位数，因此，要按k1、k2、......、kn-1的值从右向左确定n、n-1、......、2的位置，并逐个放置在排列中：i放在右起的ki+1位，如果某位已放有数字，则该位置不算在内，最后一个空位放1。 因此从67342300可得到排列849617523，它就是839647521的后一个排列。因为9最先放置，k1=6，9 放在右起第7位，空出6个空位，然后是放8，k2=7，8放在右起第8位，但9占用一位，故8应放在右起第9位，余类推。 程序代码如下： Private Sub Incr(p() As Integer, ByVal n As Integer) Dim m() As Integer '保存中介数的数组 Dim i As Integer, j As Integer Dim a As Integer ReDim m(n) For i = 1 To n '第一个排列的中介数为000 0 m(i) = 0 Next Do While n > 0 For i = 1 To n '排列的各位为0 p(i) = 0 Next For i = 1 To n '从右向左察看排列中为0的位 a = m(i) + 1 j = n Do While j > 0 If p(j) = 0 Then a = a - 1 If a = 0 Then Exit Do '0的个数决定数字i的位置 End If j = j - 1 Loop p(j) = n - i + 1 '将数字i放置在指定位置Next OutL p If MedN(m) Then Exit Do '计算下一个中介数，如果是00...0，则全部排列找到Loop End Sub Private Function MedN(m() As Integer)As Boolean '计算中介数函数 Dim i As Integer, sum As Integer Dim b As Boolean b = False i = n - 1 Do While i > 0 m(i) = m(i) + 1 If m(i) < n - i + 1 Then Exit Do m(i) = 0 i = i - 1 Loop Sum = 0 For i = 1 To n - 1 '计算中介数各位之和 Sum = Sum + m(i) Next If Sum = 0 Then b = True '中介数各位之和为0 MedN = b End Function 3.递减进位制数法 在递增进位制数法中，中介数的最低位是逢2进1，进位频繁，这是一个缺点。把递增进位制数翻转,就得到递减进位制数。 839647521的中介数是67342221(k1k2…kn-1)，倒转成为12224376(kn-1…k2k1)，这是递减进位制数的中介数：ki(i=n-1,n-2,…,2)位逢i向ki-1位进1。给定排列p，p的下一个排列的中介数定义为p的中介数加1。例如p=839647521，p 的中介数为12224376，p的下一个排列的中介数为12224376+1=12224377，由此得到p的下一个排列为893647521。 给定中介数，可用与递增进位制数法类似的方法还原出排列。但在递减进位制数中，可以不先计算中介数就直接从一个排列求出下一个排列。具体算法如下： 1）如果p(i)=n且i<>n，则p(i)与p(i-1)交换 2）如果p(n)=n，则找出一个连续递减序列9、8、......、i，将其从排列左端删除，再以相反顺序加在排列右端，然后将i-1与左边的数字交换 例如p=893647521的下一个排列是983647521。求983647521的下一个排列时，因为9在最左边且第2位为8，第3位不是7，所以将8和9从小到大排于最右端364752189，再将7与其左方数字对调得到983647521的下一个排列是367452189。又例如求987635421的下一个排列，只需要将9876从小到大排到最右端并将5与其左方数字3对调，得到534216789。 程序代码如下： Private Sub Degr(p() As Integer, ByVal n As Integer) Dim i As Integer, j As Integer Do While n > 0 OutL p If p(1) = n Then '如果第一位是n i = 0 Do '从左端开始找出最长的连续递降序列 i = i + 1 If i = n Then Exit Sub Loop Until p(i) <> p(i + 1) + 1 j = i Do '找出递降序列末尾数字的下一个数字 i = i + 1 Loop Until p(i) = p(j) - 1 Swap p(i), p(i - 1) '将它与序列末尾数字交换 For i = 1 To n - j '将递减序列倒转后放置在排列右端 p(i) = p(i + j) Next For i = 1 To j p(n - i + 1) = n - i + 1 Next Else '如果最高位不是n i = 0 '从左端开始 Do '找出n所在位置 i = i + 1 Loop Until p(i) = n Swap p(i), p(i - 1) '将n与其左边数字交换 End If Loop End Sub 4.邻位对换法 邻位对换法中下一个排列总是上一个排列某相邻两位对换得到的。以4个元素的排列为例，将最后的元素4逐次与前面的元素交换，可以生成4个新排列： 1 2 3 4 1 2 4 3 1 4 2 3 4 1 2 3 然后将最后一个排列的末尾的两个元素交换，再逐次将排头的4与其后的元素交换，又生成四个新排列： 4 1 3 2 1 4 3 2 1 3 4 2 1 3 2 4 再将最后一个排列的末尾的两个元素交换，将4从后往前移： 3 1 2 4 3 1 4 2 3 4 1 2 4 3 1 2 如此循环既可求出全部排列。 程序代码如下： Private Sub Adja(p() As Integer, ByVal n As Integer) m = 1 For i = 3 To n - 1 '计算(n-1)!/2 m = m * i Next For i = 1 To m - 1 OutL p For j = n To 2 Step -1 '将n从排列尾逐位向前移 Swap p(j), p(j - 1) OutL p '移动一次产生一个新排列 Next Swap p(n), p(n - 1) OutL p For j = 1 To n - 1 '将n从排列头逐位向后移 Swap p(j), p(j + 1) OutL p '移动一次产生一个新排列 Next Swap p(1), p(2) Next End Sub 5.元素增值法（n进制法） 1）从原始排列p=p1p2......pn开始，第n位加n-1，如果该位的值超过n，则将它除以n，用余数取代该位，并进位（将第n-1位加1） 2）再按同样方法处理n-1位，n-2位，......，直至不再发生进位为止，处理完一个排列就产生了一个新的排列 3）将其中有相同元素的排列去掉 4）当第一个元素的值>n则结束 以3个数1、2、3的排列为例：原始排列是1 2 3，从它开始，第3个元素是3，3+2=5，5 Mod 3=2，第2个元素是2，2+1=3，所以新排列是1 3 2。通过元素增值，顺序产生的排列是：1 2 3，1 3 2，2 1 1，2 1 3，2 2 2，2 3 1，2 3 3，3 1 2，3 2 1 有下划线的排列中存在重复元素，丢弃，余下的就是全部排列。 Private Sub Incr(p() As Integer, ByVal n As Integer) Dim i As Integer, j As Integer Do While n > 0 OutL p Nextn: p(n) = p(n) + n - 1 '第n个元素增值n-1 For j = n To 2 Step -1 '从后往前检查 If p(j) > n Then '如果元素增值后超过n p(j) = p(j) Mod n '用n除它取余数 p(j - 1) = p(j - 1) + 1 '向前一个元素进位 If p(1) > n Then Exit Sub '第一个元素值超过n，则所有排列都找到 End If Next For i = 1 To n - 1 '检查排列中的元素是否重复 For j = i + 1 To n If p(i) = p(j) Then GoTo Nextn '排列中有重复元素，丢弃 Next Next Loop End Sub 6.递归类算法 全排列的生成方法用递归方式描述比较简洁，实现的方法也有多种。 1）回溯法 回溯法通常是构造一颗生成树。以3个元素为例；树的节点有个数据，可取值是1、2、3。如果某个为0，则表示尚未取值。 初始状态是(0，0，0)，第1个元素值可以分别挑选1，2，3，因此扩展出3个子结点。用相同方法找出这些结点的第2个元素的可能值，如此反复进行，一旦出现新结点的3个数据全非零，那就找到了一种全排列方案。当尝试了所有可能方案，即获得了问题的解答。 程序代码如下： Private Sub Remo(p() As Integer, ByVal k As Integer) Dim b As Boolean If k = n + 1 Then '如果k>n则输出一个排列 OutL p Else '否则 For i = 1 To n b = False '重复元素标志置为False p(k) = i '第k个元素设为i For j = 1 To k - 1 '检查是否存在重复元素 If i = p(j) Then '有重复 b = True '设置重复标志为True j = k - 1 '回溯 End If Next '换一个元素试探 If Not b Then Remo, k + 1 '无重复，继续递归找下一个元素 Next End If End Sub 2）递归算法 如果用P表示n个元素的排列，而Pi表示不包含元素i的排列，(i)Pi表示在排列Pi前加上前缀i的排列，那么，n个元素的排列可递归定义为： 如果n=1，则排列P只有一个元素i 如果n>1，则排列P由排列(i)Pi构成（i=1、2、....、n-1）。 根据定义，容易看出如果已经生成了k-1个元素的排列，那么，k个元素的排列可以在每个k-1个元素的排列Pi前添加元素i而生成。例如2个元素的排列是1 2和2 1，对与个元素而言，p1是2 3和3 2，在每个排列前加上1即生成1 2 3和1 3 2两个新排列，p2和p3则是1 3、3 1和1 2、2 1，按同样方法可生成新排列2 1 3、2 3 1和3 1 2、3 2 1。 程序代码如下： Private Sub Recu(p() As Integer, ByVal k As Integer) If k = n Then OutL p Else For i = k To n Swap p(k), p(i) Recu p, k + 1 Swap p(k), p(i) Next End If End Sub 3）循环移位法 如果已经生成了k-1个元素的排列，则在每个排列后添加元素k使之成为k个元素的排列，然后将每个排列循环左移（右移），每移动一次就产生一个新的排列。 例如2个元素的排列是1 2和2 1。在1 2 后加上3成为新排列1 2 3，将它循环左移可再生成新排列2 3 1、3 1 2，同样2 1 可生成新排列2 1 3、1 3 2和3 2 1。 程序代码如下： Private Sub Cycl(p() As Integer,ByVal k As Integer) If k > n Then OutL p tot = tot + 1 Else For i = 0 To k - 1 t = p(1) For j = 2 To k p(j - 1) = p(j) Next p(k) = t Cycl p,k + 1 Next End If End Sub 排列组合n选m，组合算法——0-1转换算法（巧妙算法）C++实现 知识储备 排列的定义：从n个不同元素中，任取m(m≤n,m与n均为自然数,下同）个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(m≤n）个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 A(n,m）表示计算公式： 注意：m中取n个数，按照一定顺序排列出来，排列是有顺序的，就算已经出现过一次的几个数。只要顺序不同，就能得出一个排列的组合，例如1,2,3和1,3,2是两个组合。 组合的定义：从n个不同元素中，任取m(m≤n）个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n）个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。用符号 C(n,m) 表示。 计算公式： 注意：m中取n个数，将他们组合在一起，并且顺序不用管，1,2,3和1,3,2其实是一个组合。只要组合里面数不同即可 组合算法 本算法的思路是开两个数组，一个index[n]数组，其下标0~n-1表示1到n个数，1代表的数被选中，为0则没选中。value[n]数组表示组合 的数值，作为输出之用。 ? 首先初始化，将index数组前m个元素置1，表示第一个组合为前m 个数,后面的置为0。? 然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为?“01”组合，同时将其左边的所有“1”全部移动到数组的最左端。一起得到下一个组合（是一起得出，是一起得出，是一起得出）重复1、2步骤，当第一个“1”移动到数组的n-m的位置，即m个“1”全部移动到最右端时；即直到无法找到”10”组合,就得到了最后一个组合。 组合的个数为： 例如求5中选3的组合： 1 1 1 0 0 --1,2,3? 1 1 0 1 0 --1,2,4? 1 0 1 1 0 --1,3,4? 0 1 1 1 0 --2,3,4? 1 1 0 0 1 --1,2,5? 1 0 1 0 1 --1,3,5? 0 1 1 0 1 --2,3,5? 1 0 0 1 1 --1,4,5? 0 1 0 1 1 --2,4,5? 0 0 1 1 1 --3,4,5 代码如下： 第一章算法概述 1.算法：解决问题的一种方法或过程；由若干条指令组成的有穷指令。 2.算法的性质： 1)输入：有零个或多个输入 2)输出：有至少一个输出 3)确定性：每条指令是清晰的、无歧义的 4)有限性：每条指令的执行次数和时间都是有限的 3.算法与程序的区别 程序是算法用某种程序设计语言的具体实现 程序可以不满足算法的有限性 4.算法复杂性分析 1)算法的复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复 杂性，需要空间资源的量称为空间复杂性 2)三种时间复杂性：最坏情况、最好情况、平均情况 3)可操作性最好且最有实际价值的是最坏情况下的时间复杂性 第二章递归与分支策略 1.递归概念：直接或间接调用自身的算法 2.递归函数：用函数自身给出定义的函数 3.递归要素：边界条件、递归方程 4.递归的应用 ?汉诺塔问题 void Hanuo(int n,int a,int b,int c) { if(n==1) return; Hanuo(n-1,a,c,b); move(a,b) Hanuo(n-1,c,b,a); } ?全排列问题 void Perm(Type list[],int k,int m) { //产生list[k,m]的所有排列 if(k == m) { for(int i = 0;I <= m;i++) cout< 字符串的排列组合算法合集 全排列在笔试面试中很热门，因为它难度适中，既可以考察递归实现，又能进一步考察非递归的实现，便于区分出考生的水平。所以在百度和迅雷的校园招聘以及程序员和软件设计师的考试中都考到了，因此本文对全排列作下总结帮助大家更好的学习和理解。对本文有任何补充之处，欢迎大家指出。 首先来看看题目是如何要求的（百度迅雷校招笔试题）。一、字符串的排列 用C++写一个函数, 如 Foo(const char *str), 打印出 str 的全排列,如 abc 的全排列: abc, acb, bca, dac, cab, cba 一、全排列的递归实现 为方便起见，用123来示例下。123的全排列有123、132、213、231、312、321这六种。首先考虑213和321这二个数是如何得出的。显然这二个都是123中的1与后面两数交换得到的。然后可以将123的第二个数和每三个数交换得到132。同理可以根据213和321来得231和312。因此可以知道——全排列就是从第一个数字起每个数分别与它后面的数字交换。找到这个规律后，递归的代码就很容易写出来了： view plaincopy #includeiostream?using?namespace?std;?#includeassert.h?v oid?Permutation(char*?pStr,?char*?pBegin)?{?assert(pStr?pBe gin);?if(*pBegin?==?'0')?printf("%s",pStr);?else?{?for(char *?pCh?=?pBegin;?*pCh?!=?'0';?pCh++)?{?swap(*pBegin,*pCh);?P ermutation(pStr,?pBegin+1);?swap(*pBegin,*pCh);?}?}?}?int?m ain(void)?{?char?str[]?=?"abc";?Permutation(str,str);?retur n?0;?}? 另外一种写法： view plaincopy --k表示当前选取到第几个数，m表示共有多少个数?void?Permutation(char*?pStr,int?k,int?m)?{?assert(pStr); ?if(k?==?m)?{?static?int?num?=?1;?--局部静态变量，用来统计全排列的个数?printf("第%d个排列t%s",num++,pStr);?}?else?{?for(int?i?=?k;?i?=?m;?i++)?{?swa p(*(pStr+k),*(pStr+i));?Permutation(pStr,?k?+?1?,?m);?swap( *(pStr+k),*(pStr+i));?}?}?}?int?main(void)?{?char?str[]?=?" abc";?Permutation(str?,?0?,?strlen(str)-1);?return?0;?}? 如果字符串中有重复字符的话，上面的那个方法肯定不会符合要求的，因此现在要想办法来去掉重复的数列。二、去掉重复的全排列的递归实现 由于全排列就是从第一个数字起每个数分别与它后面的数字交换。我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这二个数就不交换了。如122，第一个数与后面交换得212、221。然后122中第二数就不用与第三个数交换了，但对212，它第二个数 全排列的生成算法对于给左的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。字典序法按照字典序求下一个排列的算法广例字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是：123,132,213,231,312,321o注意一个全排列可看做一个字符串，字符串可有前缀、后缀/生成给泄全排列的下一个排列所谓一个全排列的下一个排列就是这一个排列与下一个排列之间没有其他的排列。这就要求这一个排列与下一个排列有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。广例839647521是1—9的排列。1—9的排列最前而的是123456789,最后而的是987654321,从右向左扫描若都是增的，就到了987654321,也就没有下一个了。否则找出第一次出现下降的位置。算法：由P1P2...Pn生成的下一个排列的算法如下：1求j=max{j| Pj-I 字符串全排列算法C语言实现 问题描述： 输入一个字符串，打印出该字符串中字符的所有排列。 输入: 123 输出: 123 132 213 231 312 321 问题分析： 现象分析： 这种问题，从直观感觉就是用递归方法来实现即：把复杂问题逐渐简单化，进而得出具体代码实现。（如何发现一个问题可以使用递归方式来解决？经分析可以发现：M 个数的排列方法与N(N>M)个数的排列方法没有区别，处理方法与数据的个数没有关系。 处理方法的一致性，就可以采用递归）。 3个数（123）排列，第一位1不动，剩下两个数（23）的排列，只要相互颠倒一下，就可以出现关于1开头的所有排列 123 132 把2换到第一位，保持不动，剩下的两个数（13）的排列，只要相互颠倒一下，就可以出现关于2开头的所有排列 213 231 同理，把3换到第一位，可得到 312 321 扩展： 把3个数的所有排列，前面加一个4，就可以得到关于4开头的所有的排列4123 4132 4213 4231 4312 4321 若把4与后续数据中的任意一个数据交换，通过完成对后续三个数的全排列，就可以得到相应的数开头的四数的排列。 总结： 对4个数的排列，可以转换成首位不动，完成对3个数的排列 对3个数的排列，可以转换成首位不动，完成对2个数的排列 对2个数的排列，可以转换成首位不动，完成对1个数的排列 对于1个数，无排列，直接输出结果 算法实现说明： 对n个数的排列，分成两步： （1）首位不动，完成对n-1个数的排列， （2）循环将后续其他数换到首位，再次进行n-1个数的排列 注：排列完成后，最终的串要与原串相同 C语言代码实现： #include 算法设计与分析期末综合实验试题清单 分治与递归 1-1 合并排序 问题描述：给定n 个整数，利用合并排序思想将其调整成单调序列。 输入：整数的个数n ，以及n 个整数 输出：从大到小排序的n 个整数（或从小到大排序） 1-2 split 快速排序（枢点法） 问题描述：给定n 个整数，利用枢点法快速排序的思想将其调整成单调序列。 输入：整数的个数n ，以及n 个整数 输出：从大到小排序的n 个整数（或从小到大排序） 1-3 平面最近点对 问题描述：平面内有若干点，设计一算法在O （nlogn ）时间内求出直线距离最近的一对点，并输它们的距离。 输入：点对的数目n 以及n 对点的坐标 输出：最近的点对坐标（x,y ）以及距离d 1-4 棋盘覆盖问题 问题描述：在一个2k ×2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该 方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L 型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L 型骨牌不得重叠覆盖。 输入：棋盘的行列数n ，棋盘中特殊方格的行列号（x,y ） 输出：棋盘的覆盖方案 1-5 求k 大（小）元素（基于split 枢点法划分） 问题描述：有一数列，设计一分治递归算法，以Ω(nlogn)时间找出其第k 大（小）元素。 输入：整数的个数n 、n 个整数以及k 值 输出：第k 大（小）元素值以及其对应的下标i 1-6 二分检索 问题描述：有一单调序列，设计一分治算法检索出元素x 。 输入：整数的个数n、n个单调增（减）个整数以及需检索的元素值x 输出：最近的点对坐标（x,y）以及距离d 1-7 大整数乘法（10进制） 问题描述：有两个10制的大整数（不少于30位），设计一分治算法，以O（nlogn）时间算出其乘积。 输入：第一个大整数的位数m、第二个大整数的位数n，以及两个大整数x,y 输出：两个大整数的乘积s 1-8 循环赛比赛安排 问题描述：设计一个满足以下要求的比赛日程表： (1)每个选手必须与其他n-1个选手各赛一次； (2)每个选手一天只能赛一次； (3)循环赛一共进行n-1天。 输入：选手的个数n、n个选手的编号 输出：每天的赛事安排(共n-1天） 1-9 整数的划分问题 问题描述：将正整数n表示成一系列正整数之和：n=n1+n2+…+n k，其中n1≥n2≥…≥n k≥1，k≥1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数以及划分情况。 输入：正整数n 输出：n的划分个数以及划分情况 1-10 主元素问题 问题描述：有一个整数数列，数列中元素出现次数超过一半的元素定义为主元素，设计一分治算法，求出主元素。 输入：整数的个数n以及n个整数 输出：如果有主元素，输出主元素以及它们所在的位置；如果没有主元素，输出-1 1-11 全排列的生成 问题描述：给出一个序列，生成这个序列的全排列 输入：整数的个数n以及n个整数 输出：生成这n个数的全排列 贪婪算法 2-1 加油站问题 问题描述：一辆汽车加满油后,可行使n千米。旅途中有若干个加油站。若要使沿途加油次数最少,设计一个有效算法，对于给定的n和k个加油站位置，指出应在哪些加油站停靠加油才能使加油次数最少。 输入：汽车加满油后可行驶千米数n，加油站个数k。以及两两加油站之间的距离。 输出：最少的加油次数m，如果无法到达目的地，则输出“No Solution”。 1.5全排列的生成算法 全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。 这里介绍全排列算法四种： (A)字典序法 (B)递增进位制数法 (C)递减进位制数法 (D)邻位对换法 1.5.1字典序法 对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。 [例]字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列 是:123,132,213,231,312,321。 [注意] 一个全排列可看做一个字符串，字符串可有前缀、后缀。 1）生成给定全排列的下一个排列所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。[例]839647521是1--9的排列。1—9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。 / 1.5.2递增进位制数法 1)由排列求中介数 在字典序法中，中介数的各位是由排列数的位决定的.中介数位的下标与排列的位的下标一致。 在递增进位制数法中，中介数的各位是由排列中的数字决定的。即中介数中各位的下标与排列中的数字(2—n)一致。可看出n-1位的进位链。右端位逢2进1，右起第2位逢3进1，…，右起第i位逢i+1进1，i=1,2,…,n-1. 这样的中介数我们称为递增进位制数。上面是由中介数求排列。 由序号（十进制数）求中介数（递增进位制数）如下： m=m1,0≤m≤n!-1 m1=2m2+kn-1,0≤kn-1≤1 m2=3m3+kn-2,0≤kn-2≤2 …………… mn-2=(n-1)mn-1+k2,0≤k2≤n-2 mn-1=k1,0≤k1≤n-1 p1p2…pn←→(k1k2…kn-1)↑←→m 在字典序法中由中介数求排列比较麻烦，我们可以通过另外定义递增进位制数加以改进。为方便起见，令ai+1=kn-1，i=1,2,…,n-1 (k1k2…kn-1)↑=(anan-1…a2)↑ ai：i的右边比i小的数字的个数 在这样的定义下， 有839647521←→(67342221)↑ 全排列的生成算法对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。字典序法按照字典序求下一个排列的算法 /*例字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。注意一个全排列可看做一个字符串，字符串可有前缀、后缀。*/生成给定全排列的下一个排列所谓一个全排列的下一个排列就是这一个排列与下一个排列之间没有其他的排列。这就要求这一个排列与下一个排列有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。/*例 839647521是1—9的排列。1—9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。算法: 由P1P2…Pn 生成的下一个排列的算法如下:1. 求i=max{j| Pj-1 第一次看到这个算法是在软件设计师的辅导书上。代码如下，在VC++ 7.0下调试通过。// Permutation.cpp : 定义控制台应用程序的入口点。 // //N个数全排列的非递归算法 #include “stdafx.h” void swap(int &a, int &b) { int temp; temp = a; a = b; b = temp; } /* 根据当前的排列p，计算下一个排列。 原则是从1234–>4321，若p已经是最后一个排列，传回false，否则传回true。 p是一个n维向量。 */ bool nextPermutation(int *p, int n) { int last = n –1; int i, j, k; //从后向前查找，看有没有后面的数大于前面的数的情况，若有则停在后一个数的位置。 i = last; while (i > 0 && p[i] < p[i - 1]) i–; //若没有后面的数大于前面的数的情况，说明已经到了最后一个排列，返回false。 if (i == 0) return false; //从后查到i，查找大于p[i - 1]的最小的数，记入k k = i; for (j = last; j >= i; j–) if (p[j] > p[i - 1] && p[j] < p[k]) k = j; //交换p[k]和p[i - 1] swap(p[k], p[i - 1]); //倒置p[last]到p[i] for (j = last, k = i; j > k; j–, k++) swap(p[j], p[k]); 排列组合——排列公式的推理和组合 加法原理和乘法原理，是排列组合中的二条基本原理，在解决计数问题中经常运用。掌握这两条原理，并能正确区分他们，至关重要。 加法原理 若完成一件事情有3类方式，其中第一类方式有1种方法，第二类方式有3种方法，第三类有2种方法，这些方法都不相同，但任选一种方法都可以完成此事，则完成这件事情共有1+3+2=6种方法，这一原理称为加法原理。例如:从甲地到乙地有三类方式，一是汽车，二是火车，三是飞机。若一天中汽车有2班，火车有4班，飞机有一班，那么从甲地到乙地共有多少种不同的走法。共有2+4+1=7种。 乘法原理 若完成一件事情分r个步骤，其中第一个步骤有m1种方法，第二个步骤有m2种方法……第步骤共有mr种方法，各步骤连续或同时完成，这件事才算完成，则完成这件事共有m1*m2*……*mr种方法。例如:从甲地到丙地必须经过乙地。从甲地到乙地有4条路线，从乙地到丙地有3条路线，问从甲地到丙地共有多少种不同的走法？解：要从甲地到达丙地，必须经过两个步骤：先从甲地到乙地，有4条路线；再从乙地到丙地，有3条路线。只有这两个步骤都完成了，才能完成这种事情，缺少哪一个步骤都不行。因此从甲地到丙地共有4*3=12种走法。 加法原理和乘法原理的区别 以上两个基本原理在排列组合问题中将会反复使用。这两个原理回答的都是关于完成一件事情的不同方法的种数问题，但是又有根本区别。加法原理针对的是“分类”问题，若完成一件事情有多类方式，每一类方式的各种方法相互独立，用其中任何一种方法都可以完成这件事情，则用加法原理；而乘法原理针对的是“分步”问题，若完成一件事情必须依次经过多个步骤，每一个步骤的各种方法相互依存，只有各种步骤都完成才算做完成这种事情，则这时用乘法原理。 排列数公式推理过程 例：用1、2、3这3个数字可以组成多少个数字十位和个位不重复的两位数？解：要组成数字不重复的两位数，需要经过两个步骤：第一步确定十位上的数，数字1、2、3都可以放在十位上，共有3种方法；第二步确定个位上的数，因为要求个位数与十位数不能重复，所以个位上的数，只能从三个数字中去掉十位数后所剩的两个数字中任选一个，共有2种方法。只有十位和个位上的数都确定了，才能组成数字不重复的两位数，这两个步骤缺少哪一个都不行。因此，根据乘法原理，3*2=6. 上例中，我们把数字1、2、3称为元素。组成数字不重复的两位数这个问题，从3个不同的元素中任取2个，然后按顺序排成一列数，由于这样的排列与数字不重复的两位数是一一对应的，因此求数字不重复的两位数的个数等同于求这样的排列个数。 推理过程：从n个不同元素中取出m个不同元素排成一列，必须经过m 个步骤。第一步，确定第1个位置上的元素,可以从这n个元素中任取1个放在这个位置上，共有n种方法，即n-(1-1)括号内为位置数减1；第 精品文档 全排列的生成算法全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。任何n个字符集的排列都可以与1?n的n个数字的排列一一对应，因此 在此就以n 个数字的排列为例说明排列的生成法。 n 个字符的全体排列之间存在一个确定的线性顺序关系。所有的排列中除最后一个排列外，都有一个后继；除第一个排列外，都有一个前驱。每个排列的后继都可以从它的 前驱经过最少的变化而得到，全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法。 全排列的生成法通常有以下几种：字典序法递增进位数制法递减进位数制法邻位交换法 递归类算法 1. 字典序法 字典序法中，对于数字1、2、3 ......n 的排列，不同排列的先后关系是从左到右逐 个比较对应的数字的先后来决定的。例如对于5个数字的排列 1 2354和12345，排列12345 在前，排列12354 在后。按照这样的规定， 5 个数字的所有的排列中最前面的是 1 2345 ，最后面的是54321 。 字典序算法如下： 设P是1?n的一个全排列： p=p1p2 .... pn=p1p2 ...... pj-1pjpj+1 ..... p k-1pkpk+1 .... pn 1 ）从排列的右端开始，找出第一个比右边数字小的数字的序号j（j 从左端开始计算），即j=max{i|pi 1、数列全排列递归算法； 2、在不打印所有全排列时，数列长度分别为10、11、12、13时全排列花费时间测试，修改N的值重新编译即可运行测试； 3、如果需要打印全排列，打开perm函数中的注释掉的两行printf语句即可。 #include { int i = 0; if (begin == end){ for ( i = 0; i < N ; i++){ //printf("%d", list[i]); } //printf("\n"); } else{ for (i = begin; i <= end; i++) { swap(begin,i); perm(list,begin+1,end); swap(begin,i); } } } int main(int argc, char *argv[]) { int *list=a; int i; perm(list, 0, N-1); for (i = 0; i < N; i++){ printf("%d", list[i]); } return 0; } 。 算法导论复习——常见算法思想 PPT2-1： 1.堆排序（选择类排序，不稳定） （1）初始化操作：将R[1..n]构造为初始堆； （2）每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。 时间复杂度是：O（nlgn） 2.归并排序 ) 归并排序采用分治法思想的稳定的排序。算法思想是先使每个子序列有序，再使子序列段间有序。 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 重复步骤3直到某一指针超出序列尾，将另一序列剩下的所有元素直接复制到合并序列尾。 时间复杂度是：O（nlgn） 3.快速排序（交换类排序，不稳定） | （1）通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据 都比另外一部分的所有数据都要小； （2）然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 时间复杂度是：O（nlgn）。 4.分治法实现大数相乘 将a，b写成前一半数字和后一半数字相加的形式，例如若 a = 5423678，那么a1 = 542，a0 = 3678（注意若不是偶数截取较小一半） 这样a和b相乘就可以写为：a * b = { a1 * 10^(n1/2) + a0 } * { b1 * 10^(n 2/2) + b0 } （ 展开后整理得： a * b = a1*b1 * 10^[ (n1+n2)/2 ] + a1*b0 * 10^(n1/2 ) + a0*b1 * 10^(n2/2) + a0*b0 四项 这样就很容易递归的来求a * b，如果你嫌分解后的数还太大，就可以继续分解。（你可以自己规定在何时结束递归） 时间复杂度是：O（nlgn） 全排列以及相关算法 在程序设计过程中，我们往往要对一个序列进行全排列或者对每一个排列进行分析。全排列算法便是用于产生全排列或者逐个构造全排列的方法。当然，全排列算法不仅仅止于全排列，对于普通的排列，或者组合的问题，也可以解决。本文主要通过对全排列以及相关算法的介绍和讲解、分析，让读者更好地了解这一方面的知识，主要涉及到的语言是C和C++。本文的节数： 1.全排列的定义和公式： 2.时间复杂度： 3.列出全排列的初始思想： 4.从第m个元素到第n个元素的全排列的算法： 5.全排列算法： 6.全排列的字典序： 7.求下一个字典序排列算法： 8.C++ STL库中的next_permutation()函数：（#include 实验一全排列和会场安排问题 一、实验要求 1.全排列：要求键盘输入若干个不同的字符，然后产生并显示所有的排列 会场安排问题： 1.要求按贪心法求解问题； 2.要求读文本文件输入活动安排时间区间数据（数据在文件中的格式如下）； 3.不能改变活动的编号，排序时不能移动活动的所有信息； 4.按选择顺序显示活动的编号、开始时间和结束时间。 输入数据的文本文件格式：第1行为活动个数，第2行开始每行一个活动，每个活动的数据有活动编号、开始时间、结束时间，用空格隔开。 如：data.txt 18 1 6 9 2 2 7 ┋有18行 ┋ 2.18 3 5 二、实验平台 1、编程环境：Microsoft Visual Studio 2010 2、运行环境：windows7 三、核心代码 全排列： #include for ( int i = 0; i < length; i++ ) { //确ā?定¨当獭?前°结á点?的?字?符?是?什?么′，?不?能ü和í已?经-确ā?定¨的?字?符?相à同? int j; for ( j = 0; j < n; j++ ) { if ( i==record[j] ) break; } if ( j != n ) continue; //确ā?定¨当獭?前°字?符? if ( j == n ) record[n] = i; Permutation(letter,record,length,n+1); } } int _tmain(int argc, _TCHAR* argv[]) { char* letter = "abcd"; int length = strlen(letter); int* record = new int[length]; Permutation(letter,record,length,0); system("pause"); return 0; } 会场安排问题（贪心算法）： #include 排列组合算法总结(基于C++实现) 全排列n! 1.1 递归法 设一组数p = {r1, r2, r3, … ,rn}, 全排列为perm(p)，pn = p –{rn}。则perm(p) = r1perm(p1), r2perm(p2), r3perm(p3), … , rnperm(pn)。当n = 1时perm(p} = r1。 如：求{1, 2, 3, 4, 5}的全排列 1、首先看最后两个数4, 5。它们的全排列为4 5和5 4, 即以4开头的5的全排列和以5开头的4的全排列。 由于一个数的全排列就是其本身，从而得到以上结果。 2、再看后三个数3, 4, 5。它们的全排列为3 4 5、3 5 4、 4 3 5、4 5 3、 5 3 4、 5 4 3 六组数。 即以3开头的和4,5的全排列的组合、以4开头的和3,5的全排列的组合和以5开头的和3,4的全排列的组合. #include iostream using namespace std; void Perm(int start, int end, int a[]) { --得到全排列的一种情况，输出结果 if (start == end) { for (int i = 0; i end; i++) cout a[i] ' '; cout endl; for (int i = start; i end; i++) { swap(a[start], a[i]); --交换 Perm(start + 1, end, a); --分解为子问题a[start+1.,end-1]的全排列 swap(a[i], a[start]); --回溯 int main() { int i, n, a[10]; while (cin n, n) { for (i = 0; i n; i++) a[i] = i + 1; Perm(0, n, a); return 0; C(n,k)，n个数中任取k个数 2.1 递归法 实际上就是在n个数中，标记k个数，然后输出这k个数的过程。使用一个visited数组来记录相应下标的数是否被选中。 #include iostream using namespace std; void dfs(int pos, int cnt, int n, int k, int a[],bool visited[]) { --已标记了k个数，输出结果 组合数学全排列生成算法 组合数学中的全排列深成算法历来是组合数学考试的重要考察点，因此在这里我简单的介绍一下6种全排列生成算法的详细过程，并借此比较它们之间的优劣之处。 不论是哪种全排列生成算法，都遵循着“原排列”→“原中介数”→“新中介数”→“新排列”的过程。其中中介数依据算法的不同会的到递增进位制数和递减进位制数。关于排列和中介数的一一对应性的证明我们不做讨论，这里仅仅给出了排列和中介数的详细映射方法。相信熟练掌握了方法就可以顺利通过这部分的考察。 递增进位制和递减进位制数 所谓递增进位制和递减进位制数字是指数字的进制随着数字位置的不同递增或递减。通常我们见到的都是固定进制数字，如2进制，10进制等。m位n进制数可以表示的数字是m*n个。而m位递增或递减进位制数则可以表示数字m!个。例如递增进位制数4121，它的进制从右向左依次是2、3、4、5。即其最高位（就是数字4那位）最大值可能是4；第三高位最大可能是3；第二高位最大可能是2；最末位最大可能是1。如果将4121加上1的话，会使最末位得到0，同时进位；第二位的2与进位相加，也会得到0，同时进位；第三位的1与进位相加得到2，不再进位。最终得到结果是4200。递减进位制的道理是一样的，只不过进制从右向左依次是9、8、7、6……，正好与递增进位制相反。很明显，递减进位制的一个最大的好处就是加法不易进位，因为它在进行加法最频繁的末几位里（最右边）进制比较大。 接下来要了解的是递增进位制、递减进位制数和其序号的关系。递增、递减进位制数可以被看作一个有序的数字集合。如果规定递增进位制和递减进位制数的0的序号是十进制0，递增进位制数的987654321和递减进位制数的123456789对应十进制序号362880（即9!），则可以整理一套对应法则。其中，递增进位制数（a1 a2 a3 a4 a5 a6 a7 a8 a9）为： a1*9! + a2*8! + ….+ a8*2! + a9*1! =序号 例如序号100的递增进位制数就是4020，即4*4！+ 0*3！+ 2*2！+ 0*1！=100。将一个序号转换成其递增进位制数首先需要找到一个比序号小的最大阶乘数（即1、2、6、24、120、720……），对其进行整数除得到递增进位制的第一位；将除法的余数反复应用这个方法（当然，之后选择的余数是小一级的阶乘数），直到余数为0。 递减进位制数（a1 a2 a3 a4 a5 a6 a7 a8 a9）为： (((((((((a1 * 1 + a2) * 2 + a3) * 3 + …… + a7) * 8 + a8) * 9 + a9=序号 例如序号100的递减进位制数就是131（a7 a8 a9，即从后对齐），即（1*8 + 3）*9 + 1 = 100。将一个序号转换成其递减进位制数，需要对序号用9取余数，就可以得到递减进位制的最末位（这点和递增进位制先算出最高位相反）。用余下的数的整数除结果重复此过程（当然，依次对8、7、6……取余），直到余数为0。 关于递增进位制和递减进位制需要注意的重点：一是其加减法的进位需要小心；二是序号和数字的转换。除了100之外，常见的转换有：999的递增数是121211，递减数是1670；99的递排 列 组 合 公 式 及 排 列 组 合 算 法
算法分析与设计总结
排 列 组 合 公 式 及 排 列 组 合 算 法 ( 2 0 2 0 )
全排列生成算法
补充全排列算法C语言实现
算法设计与分析
全排列问题的解析
全排列生成算法
全排列生成数字或者字母
排 列 组 合 公 式 及 排 列 组 合 算 法
全排列的生成算法
c语言递归算法实现数列全排列
算法分析与设计常见算法思想
全排列算法解析(完整版)
算法实验报告1 全排列和会场安排问题
排 列 组 合 公 式 及 排 列 组 合 算 法
组合数学中的全排列生成算法完整版
相关文档
- 非递归全排列_算法分析与设计实验
- 全排列算法
- 算法设计与分析全排列问题.
- 补充全排列算法C语言实现
- 全排列算法解析(完整版)
- 组合数学中的全排列生成算法完整版
- 排列组合生成算法
- 排列组合生成算法C++实现之字典序法
- 算法设计与分析全排列问题
- 1.5 组合数学之全排列的生成算法
- 排 列 组 合 公 式 及 排 列 组 合 算 法 ( 2 0 2 0 )
- 排 列 组 合 公 式 及 排 列 组 合 算 法 ( 2 0 2 0 )
- 全排列的生成算法
- 1.5 全排列的生成算法
- 排列组合生成算法
- 全排列生成数字或者字母
- 组合数学 第一章 排列组合5全排列的生成算法合
- 全排列算法解析(完整版)
- 全排列算法原理和实现
- 全排列生成算法