文档库 最新最全的文档下载
当前位置:文档库 › 全排列算法解析

全排列算法解析

全排列算法解析
全排列算法解析

全排列以及相关算法

在程序设计过程中,我们往往要对一个序列进行全排列或者对每一个排列进行分析。全排列算法便是用于产生全排列或者逐个构造全排列的方法。当然,全排列算法不仅仅止于全排列,对于普通的排列,或者组合的问题,也可以解决。本文主要通过对全排列以及相关算法的介绍和讲解、分析,让读者更好地了解这一方面的知识,主要涉及到的语言是C和C++。本文的节数:

1.全排列的定义和公式:

2.时间复杂度:

3.列出全排列的初始思想:

4.从第m个元素到第n个元素的全排列的算法:

5.全排列算法:

6.全排列的字典序:

7.求下一个字典序排列算法:

8.C++ STL库中的next_permutation()函数:(#include

9.字典序的中介数,由中介数求序号:

10.由中介数求排列:

11.递增进位制数法:

12.递减进位制数法:

13.邻位对换法:

14.邻位对换法全排列:

15.邻位对换法的下一个排列:

16.邻位对换法的中介数:

17.组合数的字典序与生成:

由于本文的,内容比较多,所以希望读者根据自己的要求阅读,不要一次性读完,有些章节可以分开读。第1节到第5节提供了全排列的概念和一个初始的算法。第6节到第8节主要讲述了字典序的全排列算法。第9到第10节讲了有关字典序中中介数的概念。第11到第12节主要介绍了不同的中介数方法,仅供扩展用。第13节到15节介绍了邻位对换法的全排的有关知识。16节讲了有关邻位对换法的中介数,仅供参考。第17节讲了组合数生成的算法。

1.全排列的定义和公式:

从n个数中选取m(m<=n)个数按照一定的顺序进行排成一个列,叫作从n个元素中取m 个元素的一个排列。由排列的定义,显然不同的顺序是一个不同的排列。从n个元素中取m 个元素的所有排列的个数,称为排列数。从n个元素取出n个元素的一个排列,称为一个全排列。全排列的排列数公式为n!,通过乘法原理可以得到。

2.时间复杂度:

n个数(字符、对象)的全排列一共有n!种,所以全排列算法至少时O(n!)的。如果要对全排列进行输出,那么输出的时间要O(n*n!),因为每一个排列都有n个数据。所以实际上,全排列算法对大型的数据是无法处理的,而一般情况下也不会要求我们去遍历一个大型数据的全排列。

3.列出全排列的初始思想:

解决一个算法问题,我比较习惯于从基本的想法做起,我们先回顾一下我们自己是如何写一组数的全排列的:1,3,5,9(为了方便,下面我都用数进行全排列而不是字符)。

1,3,5,9.(第一个)

首先保持第一个不变,对3,5,9进行全排列。

同样地,我们先保持3不变,对5,9进行全排列。

保持5不变,对9对进行全排列,由于9只有一个,它的排列只有一种:9。接下来5不能以5打头了,5,9相互交换,得到

1,3,9,5.

此时5,9的情况都写完了,不能以3打头了,得到

1,5,3,9

1,5,9,3

1,9,3,5

1,9,5,3

这样,我们就得到了1开头的所有排列,这是我们一般的排列数生成的过程。再接着是以3、5、9打头,得到全排列。这里还要注意的一点是,对于我们人而言,我们脑子里相当于是储存了一张表示原有数组的表,1,3,5,9,1开头的所有排列完成后,我们选择3开头,3选完了之后,我们选择5开头,而不会再返过来选1,而且知道选到9之后结束,但对于计算机而言,我们得到了3,5,1,9后,可能再次跳到1当中,因为原来数组的顺序它已经不知道了,这样便产生了错误。对于算法的设计,我们也可以维护这样一个数组,它保存了原始的数据,这是一种方法。同时我们还可以再每次交换后再交换回来,变回原来的数组,这样程序在遍历的时候便不会出错。读者可以练习一下这个过程,思考一下你是如何进行全排列的,当然,你的方法可能和我的不太一样。

我们把上面全排列的方法归纳一下,基本上就是:任意选一个数(一般从小到大或者从左到右)打头,对后面的n-1个数进行全排列。聪明的读者应该已经发现,这是一个递归的方法,因为要得到n-1个数的全排列,我们又要先去得到n-2个数的全排列,而出口是只有1个数的全排列,因为它只有1种,为它的本身。写成比较规范的流程:

1.开始for循环。

2.改变第一个元素为原始数组的第一个元素(什么都没做)。

3.求第2个元素到第n个元素的全排列。

4.要求第2个元素到第n个元素的全排列,要递归的求第3个元素到第n个元素的全排列。......

5.直到递归到第n个元素到第n元素的全排列,递归出口。

6.将改变的数组变回。

7.改变第一个元素为原始数组的第二个元素。

(注:理论上来说第二次排列时才改变了第一个元素,即第6步应该此时才开始执行,但由于多执行一次无义的交换影响不大,而这样使得算法没有特殊情况,更容易读懂,如果一定要省时间可以把这步写在此处,这种算法我在下文中便不给出了,读者可以自己写。)

5.求第2个元素到第n个元素的全排列。

6.要求第2个元素到第n个元素的全排列,要递归的求第3个元素到第n个元素的全排列。......

5.直到递归到第n个元素到第n元素的全排列,递归出口。

6.将改变的数组变回。

......

8.不断地改变第一个元素,直至n次使for循环中止。

为了实现上述过程,我们要先得到从第m个元素到第n个元素的排列的算法:

4.从第m个元素到第n个元素的全排列的算法:

void Permutation(int A[], int m, int n)

{

if(m = = n)

{

Print(A); //直接输出,因为前n-1个数已经确定,递归到只有1个数。

return;

}

else

{

for(i=m;i

{

swap(a[m],a[i]); //交换,对应第二步

Permutation(A,m+1,n); //递归调用,对应三至五步

swap(a[m],a[i]); //交换,对应第六步

}

}

为了使代码运行更快,Print函数和swap函数直接写成表达式而不是函数(如果是C++的话建议把swap写成内联函数,把Print写成宏)

void Permutation(int A[], int m, int n)

{

int i, int temp;

if(m = = n)

{

for(i = 0;i

{

if(i != n-1)

printf("%d ",A[i]); //有加空格

else

printf("%d" A[i]); //没加空格

} //直接输出,因为前n-1个数已经确定,递归到只有1个数。

printf("\n");

return;

}

else

{

for(i=m;i

是递归调用,对应的是第m个元素到第n个元素的全排列。*/

{

temp = A[m];

A[m] = A[i];

A[i] = temp; //交换,对应第二步

Permutation(A,m+1,n); //递归调用,对应三至五步

temp = A[m];

A[m] = A[i];

A[i] = temp;

//交换,对应第六步

}

}

}

这个算法用于列出从第m个元素到第n个元素的所有排列,注意n不一定是指最后一个元素。算法的复杂度在于for循环和递归,最大的for是n,递归为n-1所以为

O(n*n-1*n-2*...1) = O(n!).

对上述算法进行封装,便可以得到列出全排列的函数:

5.全排列算法:

void Full_Array(int A[],int n)

{

Permutation(A, 0,n);

}

如果读者仅仅需要一个全排列的递归算法,那么看到上面就可以了。下面将对全排列的知识进行扩充。

6.全排列的字典序:

字典序的英语一般叫做dictionary order,浅显明白。

定义:对于一个序列a1,a2,a3,a4,a5....an的两个排列b1,b2,b3,b4,b5...bn和c1,c2,c3,c4,https://www.wendangku.net/doc/7518557699.html,, 如果它们的前k(常数)项一样,且c(k +1)> b(k+1),则称排列c位于排列b(关于字典序)的后面。如1,2,3,4的字典序排在1,2,4,3的前面(k=2),1,3,2,4的字典序在1,2,3,4(k=1)的后面。下面列出1,2,3按字典序的排列结果:

1,2,3

1,3,2

2,1,3

2,3,1

3,1,2

3,2,1

(有些读者会发现它们手写排列的时候也不自觉得遵照着这个规则以妨漏写,对于计算机也一样,如果有这样习惯的读者的话,那它们的实际算法更适合于表达为下面要讲的算法。)定义字典序的好处在于,排列变得有序了,而我们前面的递归算法的排列是无序的,由同一个序列生成的不同数组(排列)如1,2,3,4和2,3,4,1的输出结果的顺序是不同的,这样便没有统一性,而字典序则可以解决这个问题。很明显地,对于一个元素各不相同的元素集合,它的每个排列的字典序位置都不相同,有先有后。

接下来讲讲如何求某一个排列的紧邻着的后一个字典序。对证明不感兴趣的读者只要读下面

加色的字即可。

定理:我们先来构造这样一个在它后面的字典序,再证明这是紧邻它的字典序。对于一个排列a1,a2,a3...an,如果a(n)> a(n-1),那么a1,a2,a3...a(n),a(n-1)是它后面的字典序,否则,也就是a(n-1) > a(n),此时如果a(n-2) < a(n-1),那么在a(n-1)和a(n)中选择比a(n-2)大的较小的那个数,和a(n-2)交换,显然,它也是原排列后面的字典序。更一般地,从a(n)开始不断向前找,直到找到a(m+1) > a(m)【如果a(n) a(2) > ...a(n),是最大的字典序】,显然后面的序列满足a(m+1)>a(m+2)>...a(n).找到a(m+1)到a(n)中比a(m)大的最小的数,和a(m)交换,并把交换后的a(m+1)到a(n)按照从小到大排序,前m-1项保持不变,得到的显然也是原排列后面的字典序,这个字典序便是紧挨着排列的后一个字典序。

下面证明它是紧挨着的。1.如果还存在前m-1项和原排列相同并且也在原排列后面的字典序a1,a2,a3...bm,...,bm>原am,假设它在我们构造的字典序前面,那么必有bm < 交换后的am,但这是不可能的,因为am是后面序列中大于原来am的最小的一个,而bm必然又是后面序列中的大于am的一个元素,产生了矛盾。2.如果还存在前前m项和原排列相同并且也在原排列后面的字典序,它不可能在我们构造的字典序前面,因为我们对后面的数进行了升序排列,不存在比a(m+1)还小的数。3.如果还存在前k项(ka(k+1)[k+1 < m]对于我们构造的字典序也满足。证明完毕。

证明完成后,我们便可以通过上述的构造方法求得一个排列的下一个字典序排列了。

7.求下一个字典序排列算法:

bool Next_Permutation(int A[], int n)

{

int i,m,temp;

for(i = n-2;i >= 0;i--)

{

if(A[i+1] > A[i])

break;

}

if(i < 0)

return false;

m = i;

i++;

for(;i

if(A[i] <= A[m])

{

i--;

break;

}

swap(A[i],A[m]);

sort(A+m+1,A+n);

Print(A);

return true;

}

swap和Print函数读者可以自己写也可以参照我上面的写法,排序我这里直接使用了C++标准库中的sort,读者也可以自己写。有了这个算法后,我们便可以写一个非递归的列出全排列的方法,而且这个方法还带顺序:

void Full_Array(int A[],int n)

{

sort(A,A+n);

Print(A);

while(Next_Permutation(A,n));

}

这个算法的时间复杂度为O(n^2 + n!*n) = O(n!*n)[前面是排序的复杂度,后面是遍历O(n!)乘以输出n]。这个算法还有一个好处,那便是它可以处理元素相同的情况,不会重复输出。(之前的算法会重复,而且要注意的是,这个算法判断句中的> 、<有没有=号都是确定的,不能改,否则出现处理相同元素时便会陷入死循环,具体的写法读者可以自己举例判断,看看怎样会进入死循环。如果要使之前递归的算法不重复,在交换之前要判断相邻着的两个数是否相同,如果相同,则不交换,比如和A[i]交换,要判断A[i]是否等于A[i+1])。不过这个算法的缺陷是它把原来数组给改变了,读者可以自行在Next_Permutation当中使用int* Array = new int(sizeof(A);或者int* Array = malloc(sizeof(A)),然后把数组拷贝一遍,不对原数组进行处理,那么相应的全排列也要自己改写了,我这里就不写了。

8.C++ STL库中的next_permutation()函数:(#include

幸运的是,C++已经给我们提供了next_permutation模版函数,所以不用自己写,也就不用担心死循环的问题,不过这个函数没有输出,而是直接把数组变成了它的下一个字典序。下面给出它的源代码:

// TEMPLATE FUNCTION next_permutation

template inline

bool next_permutation(_BI _F, _BI _L)

{

_BI _I = _L; //定义新的迭代器_I并将尾地址赋给它。

if (_F = = _L || _F = = --_I) //如果首地址等于尾地址或者等于尾地址小1,直接返回false return (false); //要注意是因为我们传递的是尾地址加1(A+n = A[n]的地址),这个判断主要是考虑边界问题。

for (; ; ) //死循环,用于找到a(m+1) < a(m).

{

_BI _Ip = _I; //定义迭代器_Ip并将_I赋给它。

if (*--_I < *_Ip) //这里在比较a(m+1)和a(m)的大小,没找到则到下一个循环。如果//找到,进入条件句,由于是用了--运算符,所以得到的实际上是_Ip,也即a(m)。

{

_BI _J = _L; //定义新的迭代器_J并将尾地址赋给它,相当于从结尾开始//找。前面我的算法是从a(m+1)开始往后找,理论上从结尾开始找比较好,建议读者写的时//候也从结尾往前找。

for (; !(*_I < *--_J); ) //循环,直到找到_I<_J,由于是减减,所以得到了第一//个比_I大的元素。由于是从结尾开始找,所以加了"!",和我的相反。

;//仅仅为了找而找。。。

iter_swap(_I, _J);//a(m)和a(i)交换,相当于我写的swap语句,注意传递的是迭//代器,修改的是值。

reverse(_Ip, _L);//相比于我的全排序,直接把a(m+1)到a(n)反序更有效率。

return (true); //返回。

}

if (_I = = _F) //判断是否到起点了,相应于m+1 = 2,则把刚才反过来的反回去,//再返回false

{

reverse(_F, _L);

//有些读者喜欢在反序之前判断是否到起点,而实际上到起点的情况只有一种(最后一个),//不断地判断很浪费时间,还不如在最后再反回来。

return (false);

}

}

}

它的第一个参数是迭代器(指针、数组)的首地址,第二个参数是末地址,可以这样传递:next_permutation(A,A+n)来获得整个数组的下个字典序。我在上面已经写了完整的解释,大家可以对比我的算法和C++标准库里的算法,当然大家可以明显看到标准库算法的优越性,大家可以照着上面的解释自己写一个,不用全一样,模式一样即可,它的算法是最高效的(要不怎么能当模板?)。当然,标准库的算法为了使效率最快,安全性最高,总是喜欢用一些++啊--啊之类的运算符使得代码难读,读者在这方面可以不用模仿,算法上模仿就成了。下面再补充一些:在库中还有一个可以增加比较器的模版函数,不过实际上这个函数也不善于处理大型数据,有兴趣可以用。在C++标准库中还提供了找上一个字典序的算法,

perv_permutation(),用法一样,下面我附上原码,就不解释了,原理差不多,有兴趣的读者可以自己读读或者自己写一个。

// TEMPLATE FUNCTION prev_permutation

template inline

bool prev_permutation(_BI _F, _BI _L)

{_BI _I = _L;

if (_F == _L || _F == --_I)

return (false);

for (; ; )

{_BI _Ip = _I;

if (!(*--_I < *_Ip))

{_BI _J = _L;

for (; *_I < *--_J; )

;

iter_swap(_I, _J);

reverse(_Ip, _L);

return (true ); }

if (_I == _F)

{reverse(_F, _L);

return (false ); }}}

9.字典序的中介数,由中介数求序号:

这里我要引入一个新的概念:中介数。为什么要引入这么一个概念呢?很多时候,我们要通过一个排列得出它的字典序中的位置(序号),比如1234567应该排在第0位(开始位),1234576应该排在第1位,7654321排在第7!-1 = 5039位。当然,我们可以通过计算

Next_Permutation 函数的迭代次数来得到这个数据,但这样时间复杂度最差为O (n!),是非常不划算的,因为我们仅仅要求一个数的位置。所以我们要先从数学的角度去计算这个问题。 3456721排在第几位?

1.先看看首位3,在以3开头的数前面有以2开头和以1开头的数,这些数的个数为2*6!个,其中2代表1和2两个数。

2.再看看第二位4。如果已经确定由3开头,那么在4开头前面的数有几种呢?也是以2开头的数和以1开头的所有数,因为3已经放在开头,所以这里不算,这些数的个数为2*5!。

3.再往下看,第三位5.如果已经确定34开头,在5开头前面的有几种呢?由于3、4已经放在前面,这里还是只有1、2.这些数的个数为2*4!。

4.345已经确定,再6开头的前面有2*3!,再7开头前面有2*2!,在2开头前面有1*1!个(因为只剩1了),在1开头前面的没有了。(0*0!)

于是我们得到在3456721前面的数有2*6!+ 2*5!+ 2*4!+2*3!+2*2!+1*1 = 1745位。也说是说,在3456721前面的数一共有1745位,由于我们是从0开始的,所以它的位置也就是1745位。

上述计算过程对应了相应的算法:从高位往低位看,或者对于数组而言从序号小的往大的看,按照3,4,5,6,7,2,1[a[0],a[1],a[2],a[3],a[4],a[5],a[6]]的顺序,看它的右边比它小的数的个数k[1],k[2],k[3]...(因为左边的数已经确定了),每一位的k[i]*[(n-i-1)]! [此处n = 7]乘以它所在的位数-1的阶乘,比如3在第7位(在数组中是第0位,所以用n-0),减1得到后面还剩6位,而k[0]为2,因为在3的右边比3小的数只有两个。其它的位依次类推。为了简化公式,我们一般取i=为数组序号加1(即a[0]我们认为是a[1],用来和实际意义相近,因为我们实际中第一个数都是1而不是C 语言中的0)。得到公式:

n-1

∑k[i](n-i)!

i=1

其中i 为数组的序号,从1开始,实际写算法时应从0开始,n 为数组元素的个数,k[i]表示第i 个元素的右边(从第i+1个元素开始到数组末尾)比第i 个元素小的元素的个数。

有了上述公式,就可以方便的计算一个排列在字典序中的位置了。比如7654321

= 6 * 6!+ 5 * 5! + 4 * 4! + 3 *3! + 2*2! + 1*1! = 5039.

到此,我们给出字典序中介数的定义:

定义:由上述算法给出的数组k[i]按照顺序排列所形成的数]1[]...4[]3[]2[]1[ n k k k k k 叫做这个排列的字典序中介数。如7654321的中介数为654321,3456721的中介数为222221。中介数之所以称为中介数,是因为我们知道一个排列的中介数后,便可以很方便得求得它在字典序中的序号,而这个数在实际上没有明确的意义,所以称为中介数,要注意的是,中介数

比原来排列的位数(数组的元素个数)少一位,因为最后一位的结果必然是0。读者应多多练习求一个排列的中介数以及相应的序号。以上算法的时间复杂度为)(2n O ,其中求中介数为)(2n O ,由中介数到序号为O (n )。这个算法比初始的想法的O(n!)要好的多。这个算法实际的代码我就不写了,读者可以自己写,这要是掌握这个算法的原理和过程。这里还要说的是这个算法不适合于有重复数字的情况,下面所讲的所有算法均不适合(可以想想为什么)。

10.由中介数求排列:

通过中介数可以很方便地求序号,而通过一个排列可以很方便地得到它的中介数,那么自然要想到另一个过程:通过中介数能否很方便地反推回排列呢?首先,显然地,中介数和排列是一一对应的,不存在一个中介数对应多个排列的情况(读者可以想想为什么)。所以,必然有办法可以求回去。按照我的习惯,还是从基本的想法做起,我们是怎样求得中介数的,由此反推回如何求排列。比如222221。乍一看似乎很难入手,正如微分容易而积分难一样,当然,这个逆过程比积分要简单的多,因为我们已经确定它是唯一的。

方法:从最左边开始推算:2开头,证明最高位的右边比它小的数只有两个,马上可以得到最高位是3.第二位也是2,因为3已经有了,那么还有比它小的两个数,那就是4了,以此类推,我们可以很方便地求得一个中介数的原排列。方法即从最左边推算。这是一个逆过程,最初看看是个不错的想法,做出来也比较快,而实际上不是这样的。我们看看我们实际的运算过程:最左边的数如果是x1,那么它的原排列位是x1+1,当我们去看第二个数时,我们先假想它是x2+1,如果第一个排列位比x2+1来得大,那么没有问题,如果比它小或者相等,则要加上1,所以实际上,我们每求一位数,都要先让它和前面的所有数进行比较来获得它的定位。求解中介数还有一些类似的方法,这里我便不罗列了,反正大同小异,表面上看起来比较简单,但实际实现起来是比较复杂的(由其是对计算机而言)。而且,在这种方法中,我们很难通过已知的排列序号反推出原来的排列,所以有必要给出新的中介数形式。

11.递增进位制数法:

为了改变由中介数求原排列的复杂性,我们要修改我们定义中介数的方法,我们的中介数是和相应的位数相关联的,中介数的下标对应了位的下标。我们定义一种新的中介数,称为递增进位制数,它的下标对应了数字大小(为了简便,下面还是叫做中介数,为了区分,我们把原来的中介数叫作初始中介数)。我们看一个新的数:3647521.它的初始中介数是242321(读者应该已经会求了),我们不按照从左到右的顺序排,而是按照数字的大小来排,3对应的是2,因为是原排列位上的数是3,所以把它放在第3位;6对应的是4,因为原排列位上的是6,所以把它放在第6位,4对应的是2,放在第4位,7对应3,放在第7位,5对应2,放在第5位,2对应1,放在第2位,1对应的是0,我们没有写出来。我们得到342221(0).相当于对初始中介数进行了排序,按照原来位上数字的大小排序,这样的数称为递增进位制数。读者可能还看不出来这个数和递增进位制这个名词有任何关系,它只是从中介数演变过来而已。实际上,经过这样的一个演变,每一位上的数都不会超过位的大小,比如第4位上的2(我用蓝色记号的),它是不能达到4的,因为第4位对应原排列上的4,而原排列上的4产生的初始中介数位是不可能大于4的(因为初始中介数是它右边比它小的数的个数,原排列是4,不可能有5个比它小的数)。所以就形成了递增进位制数。它的第一位恒为0,(所以用括号把0括号起来了),是个一进制数,第二位为1或0,是个二进制数,第三位为2或1或0,是个三进制数,以此类推。为了便于读者理解,我给出这样一个数的运算: 342221 (0)+ 1 = 342221 + 1(因为一进制数加任何数都相当于把它进位)= 342300.因为第二

位是个二进制数,1+1进位了,第二位为0,第三位是个3进制数,2+1还是进位了,第三位为0,第四位是个四进制数,没有进位,所以为3.得到342300。和字典序一样,对中介数加1后相当于对应的序号也加1.这个过程也不是很难,原理还是加法,只是每一位的进制都不相同,当然,如果做一个比较复杂的运算就比较难了。读者可以自己练习几个。由这样的中介数求它的序号的方法为

(((((k[1]*(n-1) + k[2])*(n-2)+k[3])*(n-3)..*2 + k[n-1].),其中k[i]就是新的中介数,i从1开始表示从左往右数,即数组的序号(对应n -i + 1位)。这里的n表示的是原排列的元素个数。

实际上就是一种奇特的进制,要注意的是,此时的序号并不是按照字典序排序的,而是一个新的排序方式。1234576 新的中介数:100000。序号:720而不是原来的1。但是范围是一样的,而且始末点是一样的。1234567 ->0 7654321->5039(读者自己算一下)。讲了这么多,读者可能觉得这个方法看着非常麻烦,它到底哪里有利于求原排列呢?下面就讲它确定原排列的方法:数空格法。

__ __ __ __ __ __ __我们画这样七个空格,来求342221的原排列:第7位数字是3,我们从右向左数3个空格,再往前数一个空格,空格中填入对应的位数7,把对应的空格擦除。

__ __ __ 7 __ __ __。第6位数字是4,我们从右向左数4个空格,其中已经放上数的不算空格,再往前数一个空格,空格中填入6,把对应空格擦除。

__ 6 __ 7 __ __ __。接下来的步骤也是一样的,第5位的数字是2,数2个空格,再往前数一个空格填入5。

__ 6 __ 7 5 __ __。第4位是2,数2个空格再往前数一个空格填入4。

__ 6 4 7 5 __ __。第3位是2,数2个空格再往前数一个空格填入3.

3 6

4 7

5 __ __。第2位是1,数1个空格,再往前数一个空格填入2.

3 6

4 7

5 2 __。第1位是0,数0个空格,再往前数一个空格填入1.

3 6

4 7

5 2 1.由此,我们得到了原来的排列3

6 4

7 5 2 1。可以看到,整个过程都是确定的,不需要进行额外的比较,相比于原来的中介数要简便得多,而且得到中介数的方法也基本类似,虽然它的本质是一个递增进制数可能有些困扰,如果不去管它的本质,则是以下简单的事情:

1.用原排列求新的中介序。

2.用中介序方便得求得原排列,使用空格法。

3.用中介序的一个公式求得新的序号。

接着还要讲讲递增中介数的最后一个好处,那便是可以方便得通过序号求回中介数。对于字典序来说,它是由几个阶乘相加得到的,反推回中介数基本上是不可能的(或者说是比较麻烦的),而对于递增进制中介数,这个过程非常的简单。通过上面的公式,我们很容易得到相逆的公式:记序号为m.

m = m1*1 + k[n]; k[n]是一进制,恒为0.

m1 = m2 * 2 + k[n-1]; 由进制的关系知道k[n-1]是二进制的0<=k[n-1]<=1

m2 = m3 * 3 + k[n-2]; 由进制的关系知道k[n-1]是三进制的0<=k[n-1]<=2

...

m(n-2) = m(n-1) * (n-1)+k[2]; 0<=k[2]<=n-2;

m(n-1) = k[1];

得到序号后,除以2取余得到k[n-1],商接着除以3取余得k[n-2],以此类推得到原中介数。由于递增进位制数法可以在原排列、中介数、序号之间进行较为方便的转换,我们可以从0开始递增中介数,进而转换为原排列并不断地求下一个序列,也可以得到全排列的算法。

不过这里我就不写了,读者有兴趣可以写写。

12.递减进位制数法:

考虑到递增进制法中由于最低位是二进制,而且低位的进制都比较低,在求下一个排列时,中介数加1往往会导致很多的进位,计算比较麻烦,所以有了递减进位,实际上就是将递增进位制的中介数倒过来即可。如342221变成122243.求序号时的公式记住也是倒过来。((((k[1]*3) + k[2])*4+k[3])*5..k[n-2]*n + k[n-1],其中k[i]就是递减进制中介数,i 从1开始表示从左往右数,即数组的序号(对应n -i + 1位)。这里的n表示的是原排列的元素个数。

如122243表示为((((1*3+2)*4+2)*5+2)*6+4)*7+3 = 4735.

由于低位都是比较高的进制,所以不容易产生进位,求下一个排列非常地简单。

我们看这个例子:122243 + 1 = 122244.这里我们不需要再进位,而是很方便的计算。122244对应的序号是4736.反过来求出原排列的方法也很简单,先反序得到递增中介数再运算即可。122244 = 442221(反序) = __ __ __ __ __ __ __ = __ __ 7 __ __ __ __ = __ 6 7__ __ __ __

= __ 6 7 __ 5__ __ = __ 6 7 4 5 __ __ = 3 6 7 4 5 2 1.(读者可以自行练习空格法)

和原来的122243对应的排列3 6 4 7 5 2 1相对比,发现仅仅是4和7交换了位置。我们可以再看看122244 +1 = 122245 = 542221(反序)= __ __ __ __ __ __ __ = __ 7 __ __ __ __ __

= __ 7 6 __ __ __ __ = __ 7 6 __ 5 __ __ = __ 7 6 4 5 __ __ = 3 7 6 4 5 2 1. 我们可以发现它仅

仅是上一个排列的6和7交换了位置。读者可能发现,如果再加两次,就会有进位,此时排列又更替了。所以,实际上,递减进位制数法的排序采用的就是这种两个相邻元素交换的方式,并且是从右往左单向交换(至于它的数学原理这里就不深究了,有兴趣的读者可以研究一下)。通过递减进位制法也可以得到全排列的算法,相比于递增进位制法较简单。13.邻位对换法:

我们从递减进制数法从得到启示,递减进制法中的交换是单向的,这导致交换到头是排列会发生更替,如果我们采用双向的交换,便可以不断地交换下去,于是产生了邻位对换法。邻位对换法在找下一个排列的方法上在很多情况下要比字典序算法要快上许多,因为每次的下一个排列只是交换两个相邻的元素,当然缺点是有到左端或者右端时要进行找最大可移动数的弊端,整体上速度和字面序算法差不多。

当然,读者可能还没有理解邻位对换法的概念,下面开始讲解。在讲解之前先介绍数学中的两个概念,不过其实在这节里没有用,下面一节才用到。

定义1:在一个序列中任意两个元素对如果满足a[k] < a[m](k < m),则称为正序,否则称为逆序。

定义2:如果一个排列中逆序的数目为奇数,则称为奇排列,若为偶数则称为偶排列。

初始的时候,我们假设这个序列是一个升序的序列,而且最小元素至少为1,升序的序列总是偶排列,并且我们设定初始所有数的移动(其实就是交换)的方向均从右向左。

我们给出可移动的概念:如果一个数沿着它的方向的邻位比它小,则称这个数是可移动的。由这个概念可以知道,1是永远不可移动的,最大的数除非是在两端而且方向指向序列外面,要不一直是可移动的。

我们再规定一个性质:如果一个可移动的数发生了移动,那么比它大的所有数的方向都反过来。对于一个排列而言,它的邻位对换法的下一个排列是最大的可移动的数移动后的结果。

我们看一个例子:

1,2,3,4.[很显然,这是一个偶排列,因为它是升序序列。1<2,1<3,1<4,2<3,2<4,3<4,都是正序]。为了得到下一个排列,我们取最大的数4,它是最大的可移动数,并把它向左移动:1,2,4,3.实际上是3和4的交换,这便是它的下一个排列。再移动:

1,4,2,3.再移动,

4,1,2,3.

由此我们得到了四个排列,每次都是通过交换相邻元素实现的。当4到头了之后,无法移动了,此时我们找到可移动的最大的数3,并把它向左移动1次,得到

4,1,3,2.

此时由于4的移动方向已经反过来了,所以最大可移动数为4,把4依次向右移动:

1,4,3,2

1,3,4,2

1,3,2,4.

4到了头,再次无法移动了,此时最大的可移动的数变成了3,把3向左移动一次,得到3,1,2,4.

此时4的移动方向再反过来向左,得到

3,1,4,2.

3,4,1,2.

4,3,1,2.

此时3也到头了,此时我们找可移动的最大的数,2.得到

4,3,2,1.

4和3的移动方向再反向右,

3,4,2,1

3,2,4,1

3,2,1,4.

4到头后,由于此时3的移动方向向右,得到

2,3,1,4.

则4的方向又反,向左移动

2,3,4,1

2,4,3,1.

4,2,3,1.

此时3再向右移动,得到

4,2,1,3.

此时4再向右移动

2,4,1,3.

2,1,4,3.

2,1,3,4.

由此,我们从一个升序排列得到了全排列。通过这个例子,读者应该可以大概了解邻位对换法的基本过程了:

1.找到最大可移动数并移动至端点

2.找到现存的最大可移动数移动一次

3.回到原最大可移动数并移动至另一端点

4.找到现存的最大可移动数移动一次

......

5.找不到最大可移动数,循环结束,遍历结束。

由这个过程也可以直接得到一个非递归的算法,首先我们要写一个找到最大可移动数并移动一次的方法:

bool Movable(int A[],direct[],int n) //direct参数用于接收每个元素移动方向的数组。

{

int max = 1;//初始化最大可移动数为1,因为规定1是最小的数,可以自己设定。

int pos = -1;//初始化最大可移动数的位置为-1.

/*下面先找到最大可移动数位置*/

for(int i=0;i

{

if(a[i] < max)

continue;

if((i < n-1 && a[i] > a[i+1] && direct[i]) || (i > 0 && a[i] >a[i-1] && ! direct[i])) {

max = a[i];

Pos = i;

}

}

/*下面对它进行移动*/

if(pos = = -1)

return false;

if(p[pos])

{

swap(A[pos],A[pos+1]);

swap(direct[pos],direct[pos+1]);//我这里用同样名字了,可以写模版,也可以改函//数名字

}

else

{

swap(A[pos],A[pos-1]);

swap(direct[pos],direct[pos-1]);//我这里用同样名字了,可以写模版,也可以改函//数名字

}

/*最后调整所有比最大可移动数大的数的方向*/

for(int i = 0;i

{

if(A[i] > max)

direct[i] = !direct[i];

}

return true;

}

有了这个方法后,便可以进行全排列了。

17.邻位对换法全排列:

void Full_Array(int A[], int n)

{

bool* direct = new bool[n]; //产生一个记录每个元素移动方向的数组

sort(A,A+n); //将原序列变成一个升序

for(int i=0;i

direct[i] = false; //初始化移动方向为false,表示从右向左。

do

{

Print(A,n);

if(A[n-1] = = n)

for(int i=n-1;i>0;i--)

{

swap(A[i],A[i-1]);

swap(direct[i],direct[i-1]); //我这里用同样名字了,可以写模版,也可以改函//数名字

Print(A,n);

}

else

for(int i=0;i < n; i++)

{

swap(A[i],A[i+1]);

swap(direct[i],direct[i+1]); //我这里用同样名字了,可以写模版,也可以改函//数名字

Print(A,n);

}

}while(Movable(A,direct,n));

delete []direct;

}

15.邻位对换法的下一个排列:

为了让读者更容易理解和掌握邻位对换法的基本过程,我先通过一个例子让大家了解如何去得到下一个排列,并接着给出了相应的算法,但是,如果我们得到了一个排列比如:

2,3,4,1.我们仅仅知道通过一次邻位交换可以得到它的下一个排列,但是是哪一位的交换呢?

首先,我们得找到最大的数的位置。2,3,4,1.中最大的数位于第3个位置。位置是好找的,那方向如何判断呢?

我们接着要判断最大的数此时的移动方向。之前给出了奇排列和偶排列的概念,在这里便用的上了。每当我们的最大的数从一端移到另一端时,就要进行最大可移动数的交换,这个过程过后,在不考虑最大数的数列中便会增加一个逆序。而初始的1,2,3的逆序为0,最大的数在移动的过程中不会改变除去最大数后的数列的顺序,所以,不考虑最大数后的数列的逆序为偶数个时(偶排列),最大数在向左移动,逆序为奇数个时(奇排列),最大数向右移动。2,3,4,1中不考虑最大数的序列2,3,1的逆序为1,所以4在向右移动。同样地,如果最大数此时在某一端点,我们可以通过上述性质判断是移动最大数还是找到最大可移动数并进行交换。当然这里我们还有问题没有解决:如何判断非最大数的数此时的方向呢?如果无法判断这个,还是无法找到下一个排列。

与上面类似地,我们可以得到更一般的结论:一个非最大数的方向由所有比它小的数构成的序列的逆序决定的,如果是偶数个时,向左,奇数个时向右[也即的所有的数包括最大数都满足这条规则]。

2,3,4,1中容易知道此时3是向右的,2是向左的,4是向左的,1是不动的。读者可以自己对1,2,3,4这个全排列的每一个进行练习。

16.邻位对换法的中介数:

邻位对换法的中介数也不难求。对于某个排列如2341,,从1开始看起(1没有方向,不用算),如果它是向左的,则右边所有比它小的数的个数为中介数的最高位,如果是向右的,则左边所有比它小的数的个数为中介数的最高位,位逐次降低,如2对应k[1] = 1,最高位为1,3对应k[2] = 1,第三位为1,4是向左的,第二位为k[3] = 1.

得到111为2341的中介数。

对应的序号的求法为

(1 * 3 + 1) * 4 + 2 = 17,和递减进位的公式一样,所以通过序号求中介数也是和递减进位、递增进位类似,除以n取余,除以n-1除余,。。。。。。

邻位对换法由中介数求原排列的方法似乎也不是很简单,读者就不用掌握了,这里就概括一下:首先要判断最大数的方向,这个和上面一样,要由其它数构成的序列的奇偶性决定,所以要求其它数构成序列的奇偶性,这个奇偶性通过求序号的公式来得到,由性质原排列中取所有小于等于k的数构成的数列(顺序不变)的奇偶性和对应的序号的奇偶性相同。我举简单的例子:2341的中介数为112.那么231的中介数为11(舍掉低相应位数即可得到相应的中介数),则它的序号为1*3+1 = 4是偶数,所以最高位的方向4的方向向左。以此类推即可。

17.组合数的字典序与生成:

最后我们讲讲组合数的生成。首先我们看看列出集合的所有子集、要列出一个集合{1,2,3,4}的所有子集是很容易的,我们可以按照二进制数的顺序,0000,0001,0010,0011,0100,0101,0110,0111......来表示我们要取的元素,其中0表示不取,1表示取,这样就获得了一个顺序。而组合也包含在这个顺序当中。我们看从{1,2,3,4}中选取两个元素的所有组合:0000 0001 0010 0011 0100 01010110 0111 1000 1001 1010 1011 1100 1101 1110 1111.

蓝色标记的是我们所取的组合。对应的顺序便是{3,4}{2,4}{2,3}{1,4}{1,3}{1,2}我们可以用字典序对这些组合进行排序:{1,2}{1,3}{1,4}{2,3}{2,4}{3,4}.共6种。按照我的习惯,我们先看看我们平常列举组合数所采取的策略。比如说1,2,3,4,5取3个元素的组合。我们先从小的取:1,2,3.再把最后一个数改变:1,2,4;1,2,5.当到达5之后,含有1,2的所有组合已经被罗列完了。改变2为3,1,3,4;1,3,5;此时我们不能再选择2进行罗列,否则会重复。改变3为4,此时2和3都不能放入,1,4,5.改变4为5时,2,3,4都不能放入,不存在组合了。这时改变1为2。之后不能再选择1罗列。所以,对于一个组合C1C2C3C4...Cr(每个代表一个数,一共r个数,代表一个组合,数从[1,n]中选),由于一个组合自身是不讲顺序的,我们可以对组合进行升序排列,使得C1

C(r - m)到达n - m后就不能再递增上去。由k = r - (r - k)得到

C(k)到达n - (r - k) = n - r + k 后就不能再递增上去。

那么,对于C1C2C3C4...Cr,我们从Cr开始向前找,直到找到有Ci < n - r + i,并执行

Ci = Ci + 1。由于所有的组合都已经强制升序,所以Cj = Ci + (j-i),j = i+1,i+2,...r即它后面

的每一项都比前一项大1。由于Ci < n -r + i,Cr = Ci + (r - i) <=n(因为Ci比原来大了1),所以构造出来的新的C1C2C3C4...Cr仍是[1,n]中选r个元素的一个组合,而且显然它在原组合的字典序后。由此,我们构造出了一个排在原组合的字典序后面的组合。接下来证明它是紧邻着原组合的。

证明:假设有一个组合B1B2B3B4...Br的前i-1个元素和C1C2C3C4...Cr一样,且在原组合字典序后,在我们构造的字典序前,那么必有新Ci > Bi > 原Ci,这是不可能的,因为新Ci = 原Ci + 1。同样不可能存在前i个元素一样但在新Ci字典序前的组合,因为强制排序后Cj 到Cr 的每个元素都是最小的。同样不可能存在前k个元素一样(k < i)但在新Ci字典序前的组合。

如果找不到有Ci < n - r + i,说明已经到达最后一个:n -r + 1,n - r + 2,...n.由此我们可以直接得到组合数的相对字典序,下一个组合的算法:

bool Next_Combination(int A[],int n,int r)

{

int i;

sort(A,A +r);

for(i = r- 1;!(A[i] < n - r + i) && i > 0;i--);

if (i = = 0)

return false;

A[i] = A[i] + 1;

for(int j=i+1;j

A[j] = A[i] + j - i;

return true;

}

当然,这个算法中的组合是从1到n中选取的。读者可以通过给自己写选取的组合规定序号进行选取,也可以自行修改算法。

排 列 组 合 公 式 及 排 列 组 合 算 法

排列组合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<

排 列 组 合 公 式 及 排 列 组 合 算 法 ( 2 0 2 0 )

字符串的排列组合算法合集 全排列在笔试面试中很热门,因为它难度适中,既可以考察递归实现,又能进一步考察非递归的实现,便于区分出考生的水平。所以在百度和迅雷的校园招聘以及程序员和软件设计师的考试中都考到了,因此本文对全排列作下总结帮助大家更好的学习和理解。对本文有任何补充之处,欢迎大家指出。 首先来看看题目是如何要求的(百度迅雷校招笔试题)。一、字符串的排列 用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,它第二个数

数据结构课程设计(内部排序算法比较_C语言)

数据结构课程设计 课程名称:内部排序算法比较 年级/院系: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语言实现

字符串全排列算法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 #include //将串左移一位,首位存到末尾。 void shift( char *s ) { if ( !s||!s[0] ) return ; //security code . null string char ch=s[0]; int i=0; while( s[++i] ) s[i-1]=s[i] ; s[i-1]=ch; } //本函数对于一个已排序好的数据进行全排列 void permutation(char list[], int head ) { int i,len; len=strlen(list) ; if ( len-head == 1 ) //后续没有再排列的,则输出排列数据 { printf( "%s\n", list ); } else { for (i = k; i

各种排序算法的总结和比较

各种排序算法的总结和比较 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个记录的关键字,依次类推,直至n-1个记录和第n个记录的关键字进行过比较为止。然后再按照上述过程进行下一次排序,直至整个序列有序为止。 1.1.2冒泡排序的特性 容易判断冒泡排序是稳定的。可以分析出它的效率,在最好情况下,只需通过n-1次比较,不需要移动关键字,即时间复杂度为O(n)(即正序);在最坏情况下是初始序列为逆序,则需要进行n-1次排序,需进行n(n-1)/2次比较,因此在最坏情况下时间复杂度为O(n2),附加存储空间为O(1)。 1.2选择排序 1.2.1选择排序的基本思想 选择排序的基本思想是[5,6]:每一次从待排序的记录中选出关键字最小的记录,顺序放在已排好序的文件的最后,直到全部记录排序完毕.常用的选择排序方法有直接选择排序和堆排序,考虑到简单和易理解,这里讨论直接选择排序。直接选择排序的基本思想是n个记录的文件的直接排序可经过n-1次直接选择排序得到有序结果。 1.2.2选择排序的特性 容易得出选择排序是不稳定的。在直接选择排序过程中所需进行记录移动的操作次数最少为0,最大值为3(n-1)。然而,无论记录的初始排序如何,所需进行的关键字间的比较次数相同,均为n(n-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|pipj} (右边的数从右至左是递增的,因此k是所有大于pj的数字中序号最大者) 3)对换pi ,pk 4 )再将pj+1 ................. pk-1pkpk+1pn 倒转得到排列p ' ' =p1p2 .... p j-1pjpn ..... pk+1pkpk-1 .... p j+1 ,这就是排列p 的下一个下一个排列。 例如839647521 是数字1?9 的一个排列。从它生成下一个排列的步骤如下:自右至左找出排列中第一个比右边数字小的数字 4 839647521 在该数字后的数字中找出比 4 大的数中最小的一个 5 839647521 将5与4交换839657421 将7421 倒转839651247 所以839647521 的下一个排列是839651 247 。 2. 递增进位数制法 在递增进位制数法中,从一个排列求另一个排列需要用到中介数。如果用ki 表示排 列p1p2...pi...pn 中元素pi 的右边比pi 小的数的个数,则排列的中介数就是对应的排 列k1 .... ki ...... kn-1 。 例如排列839647521 的中介数是72642321 ,7、2、6、..... 分别是排列中数字8、3、 1欢迎。下载

c语言递归算法实现数列全排列

1、数列全排列递归算法; 2、在不打印所有全排列时,数列长度分别为10、11、12、13时全排列花费时间测试,修改N的值重新编译即可运行测试; 3、如果需要打印全排列,打开perm函数中的注释掉的两行printf语句即可。

#include #define N 10 int a[20] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}; void swap(int one, int two) { int tmp = a[one]; a[one] = a[two]; a[two] = tmp; } void perm(int *list, int begin, int end)

{ 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; }

相关文档