全排列生成算法
全排列的生成算法对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。字典序法按照字典序求下一个排列的算法 /*例字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。注意一个全排列可看做一个字符串，字符串可有前缀、后缀。*/生成给定全排列的下一个排列所谓一个全排列的下一个排列就是这一个排列与下一个排列之间没有其他的排列。这就要求这一个排列与下一个排列有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。/*例是1—9的排列。1—9的排列最前面的是，最后面的是，从右向左扫描若都是增的，就到了，也就没有下一个了。否则找出第一次出现下降的位置。算法: 由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的下一个下一个排列。 例如是数字1～9的一个排列。从它生成下一个排列的步骤如下： 自右至左找出排列中第一个比右边数字小的数字4 在该数字后的数字中找出比4大的数中最小的一个5 将5与4交换 将7421倒转 所以的下一个排列是。 程序代码如下： 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 2 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。 例如排列的中介数是，7、2、6、......分别是排列中数字8、3、9、......的右边比它小的数字个数。 中介数是计算排列的中间环节。已知一个排列，要求下一个排列，首先确定其中介数，一个排列的后继，其中介数是原排列中介数加1，需要注意的是，如果中介数的末位kn-1+1=2，则要向前进位，一般情形，如果ki+1=n-i+1，则要进位，这就是所谓的递增进位制。例如排列的中介数是，则下一个排列的中介数是+1=（因为1+1=2，所以向前进位，2+1=3，又发生进位，所以下一个中介数是）。 得到中介数后，可根据它还原对应得排列。算法如下： 中介数k1、k2、......、kn-1的各位数字顺序表示排列中的数字n、n-1、......、2在排列中距右端的的空位数，因此，要按k1、k2、......、kn-1的值从右向左确定n、n-1、......、2的位置，并逐个放置在排列中：i放在右起的ki+1位，如果某位已放有数字，则该位置不算在内，最后一个空位放1。 因此从可得到排列，它就是的后一个排列。因为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 4 End Function 3.递减进位制数法 在递增进位制数法中，中介数的最低位是逢2进1，进位频繁，这是一个缺点。把递增进位制数翻转,就得到递减进位制数。 的中介数是(k1k2…kn-1)，倒转成为(kn-1…k2k1)，这是递减进位制数的中介数：ki(i=n-1,n-2,…,2)位逢i向ki-1位进1。给定排列p，p的下一个排列的中介数定义为p的中介数加1。例如p=，p 的中介数为，p的下一个排列的中介数为+1=，由此得到p的下一个排列为。 给定中介数，可用与递增进位制数法类似的方法还原出排列。但在递减进位制数中，可以不先计算中介数就直接从一个排列求出下一个排列。具体算法如下： 1）如果p(i)=n且i<>n，则p(i)与p(i-1)交换 2）如果p(n)=n，则找出一个连续递减序列9、8、......、i，将其从排列左端删除，再以相反顺序加在排列右端，然后将i-1与左边的数字交换 例如p=的下一个排列是。求的下一个排列时，因为9在最左边且第2位为8，第3位不是7，所以将8和9从小到大排于最右端，再将7与其左方数字对调得到的下一个排列是。又例如求的下一个排列，只需要将9876从小到大排到最右端并将5与其左方数字3对调，得到。 程序代码如下： 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 6 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个元素的排列 8 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 10 排列组合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 代码如下： 排序算法 一、插入排序(Insertion Sort) 1. 基本思想： 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。 2. 排序过程： 【示例】： [初始关键字] [49] 38 65 97 76 13 27 49 J=2(38) [38 49] 65 97 76 13 27 49 J=3(65) [38 49 65] 97 76 13 27 49 J=4(97) [38 49 65 97] 76 13 27 49 J=5(76) [38 49 65 76 97] 13 27 49 J=6(13) [13 38 49 65 76 97] 27 49 J=7(27) [13 27 38 49 65 76 97] 49 J=8(49) [13 27 38 49 49 65 76 97] Procedure InsertSort(Var R : FileType); //对R[1..N]按递增序进行插入排序, R[0]是监视哨// Begin for I := 2 To N Do //依次插入R[2],...,R[n]// begin R[0] := R[I]; J := I - 1; While R[0] < R[J] Do //查找R[I]的插入位置// begin R[J+1] := R[J]; //将大于R[I]的元素后移// J := J - 1 end R[J + 1] := R[0] ; //插入R[I] // end End; //InsertSort // 二、选择排序 1. 基本思想： 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 2. 排序过程： 【示例】： 初始关键字[49 38 65 97 76 13 27 49] 第一趟排序后13 ［38 65 97 76 49 27 49] 第二趟排序后13 27 ［65 97 76 49 38 49] 第三趟排序后13 27 38 [97 76 49 65 49] 第四趟排序后13 27 38 49 [49 97 65 76] 第五趟排序后13 27 38 49 49 [97 97 76] 第一章算法概述 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，它第二个数 数据结构课程设计 课程名称：内部排序算法比较 年级/院系：11级计算机科学与技术学院 姓名/学号： 指导老师： 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。 第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并 打印出结果。 （2）选择2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| 全排列的生成算法对于给左的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。字典序法按照字典序求下一个排列的算法广例字符集{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 快速排序（QuickSort） 快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。 （1）如果不多于1个数据，直接返回。 （2）一般选择序列最左边的值作为支点数据。（3）将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。 （4）对两边利用递归排序数列。 快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。 2 归并排序（MergeSort） 归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。 3 堆排序（HeapSort） 堆排序适合于数据量非常大的场合（百万数据）。 堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。 堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。 Shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。 Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。 5 插入排序（InsertSort） 插入排序通过把序列中的值插入一个已经排序好的序列中，直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序，或者重复排序超过200数据项的序列。 算法设计与分析期末综合实验试题清单 分治与递归 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”。 常见内部排序算法比较 排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，究竟各有什么特点呢？本文力图设计实现常用内部排序算法并进行比较。分别为起泡排序，直接插入排序，简单选择排序，快速排序，堆排序，针对关键字的比较次数和移动次数进行测试比较。 问题分析和总体设计 ADT OrderableList { 数据对象：D={ai| ai∈IntegerSet,i=1,2,…,n,n≥0} 数据关系：R1={〈ai-1，ai〉|ai-1, ai∈D, i=1,2,…,n} 基本操作： InitList(n) 操作结果：构造一个长度为n，元素值依次为1，2，…，n的有序表。Randomizel(d,isInverseOrser) 操作结果：随机打乱 BubbleSort( ) 操作结果：进行起泡排序 InserSort( ) 操作结果：进行插入排序 SelectSort( ) 操作结果：进行选择排序 QuickSort( ) 操作结果：进行快速排序 HeapSort( ) 操作结果：进行堆排序 ListTraverse(visit( )) 操作结果：依次对L种的每个元素调用函数visit( ) }ADT OrderableList 待排序表的元素的关键字为整数.用正序,逆序和不同乱序程度的不同数据做测试比较,对关键字的比较次数和移动次数(关键字交换计为3次移动)进行测试比较.要求显示提示信息,用户由键盘输入待排序表的表长(100-1000)和不同测试数据的组数(8-18).每次测试完毕,要求列表现是比较结果. 要求对结果进行分析. 详细设计 1、起泡排序 算法：核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好。 bubblesort(struct rec r[],int n) { int i,j; struct rec w; unsigned long int compare=0,move=0; for(i=1;i<=n-1;i++) for(j=n;j>=i+1;j--) { if(r[j].key 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；第 五种排序算法的分析与比较 广东医学院医学信息专业郭慧玲 摘要：排序算法是计算机程序设计广泛使用的解决问题的方法,研究排序算法具有重要的理论意义和广泛的应用价值。文章通过描述冒泡、选择、插入、归并和快速5种排序算法,总结了它们的时间复杂度、空间复杂度和稳定性。通过实验验证了5种排序算法在随机、正序和逆序3种情况下的性能,指出排序算法的适用原则,以供在不同条件下选择适合的排序算法借鉴。 关键词：冒泡排序;选择排序;插入排序;归并排序;快速排序。 排序是计算机科学中基本的研究课题之一,其目的是方便记录的查找、插入和删除。随着计算机的发展与应用领域的越来越广,基于计算机硬件的速度和存储空间的有限性,如何提高计算机速度并节省存储空间一直成为软件设计人员的努力方向。其中,排序算法已成为程序设计人员考虑的因素之一[1]，排序算法选择得当与否直接影响程序的执行效率和内外存储空间的占用量,甚至影响整个软件的综合性能。排序操作[2，3],就是将一组数据记录的任意序列,重新排列成一个按关键字有序的序列。而所谓排序的稳定性[4]是指如果在排序的序列中，存在前后相同的两个元素，排序前和排序后他们的相对位臵不发生变化。 1 算法与特性 1.1冒泡排序 1.1.1冒泡排序的基本思想 冒泡排序的基本思想是[5,6]:首先将第1个记录的关键字和第2个记录的关键字进行比较,若为逆序,则将2个记录交换,然后比较第2个和第3个记录的关键字,依次类推,直至ｎ-1个记录和第ｎ个记录的关键字进行过比较为止。然后再按照上述过程进行下一次排序,直至整个序列有序为止。 1.1.2冒泡排序的特性 容易判断冒泡排序是稳定的。可以分析出它的效率,在最好情况下,只需通过ｎ-1次比较,不需要移动关键字,即时间复杂度为Ｏ(ｎ)(即正序);在最坏情况下是初始序列为逆序,则需要进行ｎ-1次排序,需进行ｎ(ｎ-1)/2次比较,因此在最坏情况下时间复杂度为Ｏ(ｎ2),附加存储空间为Ｏ(1)。 1.2选择排序 1.2.1选择排序的基本思想 选择排序的基本思想是[5,6]:每一次从待排序的记录中选出关键字最小的记录,顺序放在已排好序的文件的最后,直到全部记录排序完毕.常用的选择排序方法有直接选择排序和堆排序,考虑到简单和易理解,这里讨论直接选择排序。直接选择排序的基本思想是ｎ个记录的文件的直接排序可经过ｎ-1次直接选择排序得到有序结果。 1.2.2选择排序的特性 容易得出选择排序是不稳定的。在直接选择排序过程中所需进行记录移动的操作次数最少为0,最大值为3(ｎ-1)。然而,无论记录的初始排序如何,所需进行的关键字间的比较次数相同,均为ｎ(ｎ-1)/2,时间 精品文档 全排列的生成算法全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。任何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; }排 列 组 合 公 式 及 排 列 组 合 算 法
各种排序算法比较
算法分析与设计总结
排 列 组 合 公 式 及 排 列 组 合 算 法 ( 2 0 2 0 )
数据结构课程设计(内部排序算法比较_C语言)
全排列生成算法
补充全排列算法C语言实现
各种排序算法的总结和比较
算法设计与分析
几种常见内部排序算法比较
全排列问题的解析
全排列生成算法
全排列生成数字或者字母
排 列 组 合 公 式 及 排 列 组 合 算 法
五种排序算法的分析与比较
全排列的生成算法
c语言递归算法实现数列全排列
相关文档
- 排列组合生成算法
- 排列组合生成算法C++实现之字典序法
- 全排列生成算法
- 排列组合生成算法C++实现之邻位互换法
- 生成排列和组合
- 全排列算法解析(完整版)
- 组合数学之排列组合生成算法
- 排列组合生成算法
- 组合数学之排列组合生成算法
- 全排列生成算法
- 排列组合生成算法之字典序法和换位法动画ppt
- 组合数学排列的逆序生成算法
- 利用排列的逆序数实现排列生成算法
- 全排列的生成算法
- 组合数学中的全排列生成算法完整版
- 排列组合生成算法
- 全排列生成算法在克莱姆法则中的应用
- 排 列 组 合 公 式 及 排 列 组 合 算 法 ( 2 0 2 0 )
- 1.5排列的生成算法
- 1.5 组合数学之全排列的生成算法