高效生成所有的排列 – huangnima

这方面的一般算法是递归,可是递归的效率略坑。另外一个经典的算法是next  permutation,即从右边开始找到第一个非增序(从右到左)的最短序列,然后将这个序列最左端的数调换为递增序中第一个比他大的数,然后将右端排序为降序(从右到左),这样就得到了比当前排列刚刚好大一点的新的排列。如此往复就可以生成所有的排列,初始的是1234…n,最后是n….4321。每次生成的过程中都需要扫描尾端得到最短序列,然后二分查找第一个比他大的数,然后替换,然后剩下的重排序(其实重排序只需要将替换之后的排列逆序就可以了)。可以看出每次生成都需要交换大于等于两个位置的数,平摊下来代价仍然很大。下文所说的生成全排列的算法,每次生成一个新的排列都只需要交换两个相邻的数,因此效率非常高。

首先,我们给出一些相关的定义。

每个生成的排列,对于这个排列中的每一个数,我们都有一个标记,代表它可以移动的方向。<号代表向左移动,>号代表向右移动。我们把这些箭头直接标在每个数字的上方,初始状态的1234…n,而且每一个数的方向都是向左。如果某个数比他箭头所指方向的相邻的数大,则我们把这个数作为可以活动的。如果箭头所指方向没有数或者比当前数小,则这个数则是不活动的。然后我们重复如下过程,每次找出最大的可活动的数,按照箭头指示将他与箭头所指相邻方向的数交换,如果当前活动的数不是n,则将不小于当前数的所有数的方向取反。如此往复,直到无法找到可以活动的数为止。

下图中代表的就是小规模下的生成过程,n分别等于2和3.

下面来证明该方法的确生成了所有的排列,对此我们采取归纳法。

首先我们可以看出对于1,2,3的时候都是成立的,其实对于1成立已经足够了。

假设对于n成立,考虑n+1的情况。

刚开始的时候我们移动n+1这个数,当这个数无法移动的时候,他在最左边,已经移动了n+1个位置。此时,这个数无法移动,然后我们开始启动小于n+1的数的移动,而这个移动方案刚好与生成n个数的排列的第一部移动方案一模一样。当移动n这个数之后,我们需要重新移动n+1这个数,因为这个数的方向已经反向了,最后移动到了最右端,共n+1个位置。然后又启动了生成n个数的全排列的第二部移动方案,如此往复。因此对于这个方案在n的时候生成的每个排列,在n+1的时候都有相对应的n+1个排列,只是n+1这个数的位置不同。由n的时候生成了n!个不同的排列,因此n+1的时候也生成了(n+1)!个不同的排列。因此,这个方案的确生成了所有的n的排列。

下面来讨论效率问题,我们每次要交换一个数的时候,都需要找到当前可移动的最大的数,如果用朴素的方法去找这个数的话,我们需要用O(n)的时间去找这个数,总共的时间花费为n*n!。事实上这个是有规律可循的,我们先看下简单情况:当n=2的时候活动序列是2;当n=3时,活动序列为33233;当n=4的时候,活动序列为44434443444244434443444。

我们开一个次数数组A[n],初始时A[k]=k-1;每次我们从这个数组中从右到左寻找第一个A[i]!=0的i,这个数就是每次我们需要移动的数。移动完之后将A[i]减去1,并把A[i+1],A[i+2]…A[n]恢复到他们的初始值。如此往复,直到找不到这个i。然后整个流程结束,由此我们得出对于i这个数,我们把这个数当作移动的数共有(i-1)*(i-1)!次,也即是i!-(i-1)!次,而每次为了得到i这个数,我们需要从右向左寻找n-i+1次,所以总共我们寻找了2*(1!+2!+….n!)次,比上述的n*n!次减少了很多。这里我们另外开一个位置数组,b[n],其中b[i]的值代表的是i这个数在当前排列中所在的位置,有了这个数组我们就好移动数了。因此每次交换两个相邻位置的数的时候,我们在交换上所花的时间为常数:交换相邻的两个数时间为3,交换相邻两个数的方向时间为3,交换B[n]这个位置索引时间也是3。因此最终的时间花费约为11*n!。

具体代码如下。

1 #include <stdio.h>
2 #include <malloc.h>
3 #define MAX 6
4 int for_out[MAX];//生成的排列数组
5 int arrow[MAX];//方向数组
6 int index[MAX];//次数数组
7 int position[MAX];//位置数组
8 int sum=0;
9
10 void out_put()//每次都输出一个排列
11 {
12 int for_j;
13 char for_k;
14 for(for_j=0;for_j<MAX;for_j++)
15 {
16 for_k=*(arrow+*(for_out+for_j))?>:<;
17 printf(%c ,for_k);
18 }
19 printf(n);
20 for(for_j=0;for_j<MAX;for_j++)
21 {
22 printf(%d ,*(for_out+for_j));
23 }
24 printf(n);
25 }
26
27 void swap(int cursor)
28 {
29 int direction,for_j,temp;
30 direction=arrow[cursor]?1:-1;
31 direction=position[cursor]+direction;
32 for_j=for_out[direction];
33 for_out[direction]=cursor;
34 for_out[position[cursor]]=for_j;
35 temp=position[cursor];
36 position[cursor]=position[for_j];
37 position[for_j]=temp;
38 }
39
40
41 int main()
42 {
43
44 int for_i,cursor;
45 for(for_i=0;for_i<MAX;for_i++)//初始化方向
46 {
47 arrow[for_i]=0;
48 }
49 for(for_i=0;for_i<MAX;for_i++)//初始化输出
50 {
51 for_out[for_i]=for_i;
52 index[for_i]=for_i;
53 position[for_i]=for_i;
54 }
55 cursor=MAX-1;
56 while(1)
57 {
58 if(index[cursor]>0)
59 {
60 if(cursor==MAX-1)
61 {
62 swap(cursor);
63 index[cursor]–;
64 out_put();
65 }
66 else
67 {
68 swap(cursor);
69 for(for_i=cursor;for_i<MAX;for_i++)
70 {
71 arrow[for_i]=1arrow[for_i];
72 }
73 out_put();
74 }
75 }
76 else
77 {
78 while(cursor>0&&index[cursor]==0)
79 {
80 cursor–;
81 }
82 if(cursor==0)
83 {
84 out_put();
85 printf(%dn,sum);
86 return 1;
87 }
88 else
89 {
90 swap(cursor);
91 index[cursor]–;
92 for(for_i=cursor+1;for_i<MAX;for_i++)
93 {
94 index[for_i]=for_i;
95 arrow[for_i]=1arrow[for_i];
96 }
97 cursor=MAX-1;
98 out_put();
99 }
100 }
101 }
102 }
103
104
105
106

 

 

本文链接:http://www.cnblogs.com/huangfeidian/p/3448604.html,转载请注明。



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量