全排列生成数字或者字母.docx

第一次看到这个算法是在软件设计师的辅导书上。代码如下，在VC+ 7.0下调试通过。/Permutation.cpp : 定义控制台应用程序的入口点。/N个数全排列的非递归算法#include “stdafx.h”voidswap(int&a,int&b)inttemp;temp=a;a=b;b=temp;/*根据当前的排列p，计算下一个排列。原则是从12344321，若p已经是最后一个排列，传回false，否则传回true。p是一个n维向量。*/boolnextPermutation(int*p,intn)intlast=n 1;inti, j, k;/从后向前查找，看有没有后面的数大于前面的数的情况，若有则停在后一个数的位置。i=last;while(i0&pi=i; j)if(pjpi-1&pjk; j, k+)swap(pj, pk);returntrue;/显示一个排列voidshowPermutation(int*p,intn)for(inti=0; in; i+)coutn;p=newanintn;for(inti=0; in; i+)pi=i+1;showPermutation(p, n);coutendl;while(nextPermutation(p, n)showPermutation(p, n);cout pi 1(1 i n 1)，反复运行nextPermuation()找出比P的“下一个”全排列，直到Pn! = p1p2pn，pi pi 1(1 i pi 1(1 i n 1)，到p1p2pn，pi pi 1(1 i n 1)。因此：1. 从低位到高位（从后向前），找出“不符合趋势”的数字。即找到一个pi，使pi 1 pi+1 pn，否则查找在in就会停下来了。这样的一个排列显然不是最小的。实际上，原来的pipn，已经是这一部分最大的一个排列了。但我们现在换了最高位pi-1，因此要让后面的数字变的最小。方法很简单，根据上面的推理，我们只须将pipn的数列倒置即可（最大的排列倒置就变成了最小的排列）。这样，我们计算出了准确的下一个排列。比如有(1,2,3,4)这样一组数1.先分成(1)和(2,3,4),然后对(2,3,4)全排列2.把(1)分别和(2,3,4)中的数对调3.比如一次调换(2),(1,3,4),然后对(2,3,4)全排列4.调换的算完了,恢复,变成(1),(2,3,4),再调换下一个(3),(1,2,4)大概就是这样的-#includestdio.hint a10,n,count=0;void perm(int k)int p,t,j;if( k=n )count+;for(p=1;p=k;p+) printf(%1d,ap);/*%1d中的数字是1，而不是字母l*/printf( );if( count%3=0 ) printf(n);return;for(j=k;j=n;j+)t=ak;ak=aj;aj=t;perm(k+1);t=ak;ak=aj;aj=t;main()int i;printf(nInput n:);scanf(%d,&n);for(i=1;i=n;i+) ai=i;perm(1);#include void swap(int &a, int &b) int temp; temp = a; a = b; b = temp;/*根据当前的排列p，计算下一个排列。原则是从12344321，若p已经是最后一个排列，传回false，否则传回true。p是一个n维向量。*/bool nextPermutation(int *p, int n) int last=n-1; int i,j,k; /从后向前查找，看有没有后面的数大于前面的数的情况，若有则停在后一个数的位置。 i=last; while(i0&pi=i; j-) if(pjpi-1&pjk; j-,k+) swap(pj,pk); */ return true;/显示一个排列void showPermutation(int *p, int n) for(int i=0; in; i+) printf(%d ,pi); printf(n);int main(int argc, char *argv) int n; int *p; scanf(%d,&n); p = new intn; for (int i = 0; i pi 1(1 i n 1)，反复运行nextPermuation()找出比P的“下一个”全排列，直到Pn! = p1p2pn，pi pi 1(1 i pi 1(1 i n 1)，到p1p2pn，pi pi 1(1 i n 1)。因此：1. 从低位到高位（从后向前），找出“不符合趋势”的数字。即找到一个pi，使pi 1 pi+1 pn，否则查找在in就会停下来了。这样的一个排列显然不是最小的。实际上，原来的pipn，已经是这一部分最大的一个排列了。但我们现在换了最高位pi-1，因此要让后面的数字变的最小。方法很简单，根据上面的推理，我们只须将pipn的数列倒置即可（最大的排列倒置就变成了最小的排列）。这样，我们计算出了准确的下一个排列。ps:这个主要的思想就是，当每次我们交换完之后，交换之后的后面的部分是一个符合趋势的排列，为了得到所有的排列，我们将其反转，那就相当于对其部分再进行一次方向最大排列的问题。倒过来再倒过去从而达到了遍历。下午偶尔翻到以前的写到的一些代码,不觉心血来潮,看了一下其中关于全排列算法的一个实现.联想到高中时数学课上学到关于组合和排列的一些公式,于是在纸上涂鸦着一些计算方法,突然灵感潮来,想借助小白鼠的那个思路也能将全排列解决出来下班回到家便赶紧吃饭玩一局sc后,开始实现,终于赶在睡觉之前可以写这篇blog,介绍我的这种还算奇妙的全排列算法:1. 算法思路: 试想N个自然数A1,A2,.,AN的全排列是N!个,那么,对于每种排列,我将其打印出来,遍历一遍至少是O(N!)的复杂度,那么能不能在就在这个复杂度内用非递归解决这个问题呢?我的想法就是从这点开始成形.同时借助了建模的思想分析的. 无论如何,我首先选取一个自然数 A1 出来,放到存放地址的中间, 那么在A1的周围存在两个位置,一个是A1的左边,一个是A1的右边,那么,我抽出另一自然数出来(假设是AK),便有两种存放的可能性:(AK,A1) , (A1,AK). 如果我将1周围的两个位置用0和1来表示,如果放在左边,那么左边用1表示,反之用0表示.反正只能放一个地方,那么这两个位置合起来不是10,就是01,化成十进制便是2或者1. 同理,如果第第二个数A2放在A1的左边,也就是第一轮获取了2,排列就是(A2,A1),当第三个数(假设是A3)到来时,那么它就存在三个位置可放了,分别是A2的左边,A2和A1之间,A1的右边,同样用0和1标志每个位置,如果A3放在A2左边,那么构成100(十进制4),如果中间则构成010(十进制2),A1的右边001(十进制1),那么可以用第二个值来表征第三个数摆放的位置. 如此,细心的玩家已经大概想明白了我要干嘛了,对,如此以往,可以将全部N个自然数用N-1个数值来替代(这些数字是有规律的,2的次方),接下来,我想到的便是,一定要找到这些数字和它在全排列中一一对应的关系,那么问题便解决了. 我们拿3个自然数的例子来分析,3!=6,对于3个自然数的全排列我将其编号1-6组,每组按上面的规则应该可以唯一对应一个序列,如将第一组对应于(1,1), 是按上面规则来的. 第二组对应于(1,2), 第三组对应于(2,1), 第四组对应于(2,2), 第五组对应于(4,1), 第六组对应于(4,2). 于是, 我只要分析出一个计算规则便可以只要遍历这N!个分组,便可以求出每个分组对应的排列了. 很显然, 由P(M,M)的计算规则,P(M,M)=M*(M-1)*.*1可以看出,如果我在第2个到来时,将m = P(M,M)%2 同时,P=P/2,那么,可以很好的处理第二个到来时所做的寻址选择:如果m是0,那么就放右边,如果m是1,就放左边,而对应于第三个到来时,同样如此,那么这个存放规则便生成了.于是遍历N!次,按辗转法则,便可以直接生成每个组对应的全排列了. 应该明白了吧?2.算法实现(C语言版): 结合上面的思路,编写代码,其中逻辑还是挺麻烦的.引用yhzhlocalhost test$ cat test_permute1.c#include #include #define N 10 /偷懒,定义个宏吧.用数组省事int permute(int perm);int main(int argc,char *argv) int ret = 0; ret = permute(N); return ret;int permute(int perm) char i = 1; int j = 1; int k = 1; int ptr2*N = 0; /其实只需要N的空间即可,未来偷懒,定义2N的数组取代队列,这也是数组替代队列的典例 while(i = perm) & (j = j*i) /这个while和下面第一个for的意思是遍历N!个数字,从1到N!,添加print语句试试 for(;k = j;k+) int begin = N; /队列的头位置(处于2N数组中的位置) int end = N; /队列的尾位置(处于数组中的位置),后面需要注意end在左边,begin在右边 int l = 1; /代排列的自然数,偷懒,就用1到N吧.方便,可以+就行了 int n = k; /辗转法则之基数 int m = 0; /辗转法则之分离数 int t = 1; /控制生成1到N个自然数的一个和K对应的排列 ptrN = l; /将数组的N位置设置为队列的头和尾所在地.同时放入第一数:1 while(t perm) /生成和K对应队列,一个一个放入2到N t+; l+; m = n%t+1; /辗转,+1为什么?呵呵,测试一下吧(注意求余可是有余数0啊) n = n/t; if( m = 1) /如果m=1,意味着n正好被t整除,那么意味着下一个数是永远放在最右边一个数的右边,因此begin+了.end不动. ptr+begin = l; else /放左边了.至于是放在左边过去的第几个位置,有m的值而定,因此会有move = begin - (m -1),因此从end到该move位置之间的所有数据要向后移动.因此会有下面的for语句,如果用队列,则不需要,数组模拟队列就是有些麻烦 int move = 0; move = begin - (m - 1); /确定放置位置 if(move end) /过end了,其实也只是过去一位,可以在这里assert一下,那么直接加.等于是在队列末尾添加数字. ptrmove = l; end = move; else /在队列中间加入数字 int index = end; for(;index=move;index+) ptrindex-1 = ptrindex; ptrmove = l; end = end - 1; /while t /循环结束 int tmp; for(tmp=end;tmp=begin;tmp+) /打印结果 printf(%d ,ptrtmp); printf( ); i+; return 0; 将宏N的值设置成适当大小,编译之后,运行试试.当然还是要惦量一下自己的机器.在我的最小配置dell latitude D620上测试的结果如下: 对于求解10个的全排列:引用yhzhlocalhost test$ time ./test_permute1 /最新的代码,非递归.10 9 8 7 6 5 2 4 3 110 9 8 7 6 5 3 4 1 210 9 8 7 6 5 3 4 2 110 9 8 7 6 5 4 1 2 310 9 8 7 6 5 4 2 1 310 9 8 7 6 5 4 1 3 210 9 8 7 6 5 4 2 3 110 9 8 7 6 5 4 3 1 210 9 8 7 6 5 4 3 2 11 2 3 4 5 6 7 8 9 10real 1m21.360suser 0m6.880ssys 0m12.921syhzhlocalhost test$ time ./test_permute1 /去掉输出real 0m1.455suser 0m1.448ssys 0m0.000s 同时,我也运行了下我很早写的那段代码:引用yhzhlocalhost test$ time ./test_permute2 /我以前写的代码,递归.10 9 8 7 6 5 3 4 1 210 9 8 7 6 5 3 4 2 110 9 8 7 6 5 4 1 2 310 9 8 7 6 5 4 1 3 210 9 8 7 6 5 4 2 1 310 9 8 7 6 5 4 2 3 110 9 8 7 6 5 4 3 1 210 9 8 7 6 5 4 3 2 1 3628800real 1m39.231suser 0m5.220ssys 0m14.889syhzhlocalhost test$ time ./test_permute2 /去掉输出real 0m0.707suser 0m0.696ssys 0m0.000s 还在网上找了段评价很不错的代码编译运行了试试:引用yhzhlocalhost test$ time ./test_permute3 /网上一个朋友的代码,递归.9 10 7 8 6 5 4 3 2 110 9 7 8 6 5 4 3 2 18 9 10 7 6 5 4 3 2 19 8 10 7 6 5 4 3 2 18 10 9 7 6 5 4 3 2 110 8 9 7 6 5 4 3 2 19 10 8 7 6 5 4 3 2 110 9 8 7 6 5 4 3 2 1real 1m41.827suser 0m6.828ssys 0m14.765syhzhlocalhost test$ time ./test_permute3 /去掉输出real 0m1.044suser 0m0.224ssys 0m0.000s 还给出一段读起来很心旷神怡的代码:引用yhzhlocalhost test$ time ./test_permute4 /呵呵,这段代码值得推敲real 0m0.219suser 0m0.196ssys 0m0.004s 列出test_permute2.c和test_permute3.c还有test_permute4.c:引用test_permute2.c#include #define N 10 /* N */#define K 10 /* K */int aK; /* 定义数组来存储中间结果 */int bK; /* 定义数组来存储结果 */int flagK; /* 定义一个标志数组 */int num; /* 计算P(NK)的值 */void print() /* 打印函数 */ int i; /for (i=0;i K;i+) / ;/printf(%3d,bi); /* 打印出结果 */ / printf( ); return; void init_abflag() int i; num=0; for (i=0;i K;i+) ai=0; /* a初始化为0 */ bi=0; /* b初始化为0 */ flagi=0; /* flag初始化为0 */ return; void perm(int k) /* 对每个组合的结果求全排列 */ int i; if (k=K) /* 输出条件 */ num+; /* 每输出一次即是一个排列 */ print(); return; for (i=0;i N;i+) if (flagi = 0) /* 这一个数值有没有用过 */ flagi+; /* 没有则用 */ bk=ai; /* 即把a中的值送给b */ perm(k+1); /* 进入递归 */ flagi-; /* 复原 */ return; void con(int n,int k) int i;/* printf( !%d! ,k);*/ if (k=0) /* 求组合，k=0,作为第一个成功返回的条件 */ perm(0); /* 对每个组合调用全排列 */ return; if (n=k) /* 求组合，k=n作为第二个成功返回的条件 */ for(i=0;i k-1;i-) /* 程序的核心部分 */ ak-1=i; /* 送入第一个数据 */ con(i-1,k-1); /* 进入递归 */ return; int main() init_abflag(); /* 初始化数组 */ con(N,K); /* 求解 */ /printf( %d,num); /* 打印出总个数 */ return 0; test_permute3.c#include #include void put(int *);int N;int main()int i,j,k,m,n,*l,*a,m