[分享]求出所有排列的非递归算法～

JAY

纯代码，看着要晕了...

Eastsun

一共才用了一个for,两个while,估计大家都看得懂吧.

不过能不能理解那是另外一回事了


[em01]

JAY

主要系不明白变量的含义...

Eastsun

//通过相邻对换产生新的置换
//对换的位置由p[]确定
//level记录变换的层数

//d用来记录变换方向

//p用于记录变换位置

ps:如果学过抽象代数里面的群论,应该会容易理解算法些,否则能看懂就说明你牛B^_^

JAY

貌似离散也讲了群论的，好像是一个叫伽罗华的人发明的那个。

Eastsun

比如“abc”的所有排列为：

abc

acb

bac

bca

cab

cba

共3！＝6个，这个问题用递归的话相对简单些（也不是很简单），这儿给出一种非递归的算法:

1. /**
   
2. @ 求出所有排列的非递归算法
   
3. */
   
4. #define MAX_N  12
   
5. long permute(int s){
   
6.     int  d[MAX_N+1],p[MAX_N+1],pos,level,n,len;
   
7.     long count;
   
8.     char str[MAX_N+2];
   
9.     char temp;
   
10.     len =strlen(s);
    
11.     if(len>MAX_N) return 0;
    
12.     strcpy(str+1,s);
    
13.     for(n=0;n＜=len;n++){
    
14.         d[n] =-1;
    
15.         p[n] =n;
    
16.     }
    
17.     count =0;
    
18.     do{
    
19.         printf("%s",str+1);
    
20.         count++;
    
21.         //if(count%5 ==0) getchar();
    
22.         printf("\n");
    
23.         level =len;
    
24.         p[level] =p[level]+d[level];
    
25.         pos =0;
    
26.         while(p[level]==0||p[level]==level){
    
27.             if(d[level]==-1) pos++;
    
28.             d[level] =-d[level];
    
29.             level--;
    
30.             p[level] =p[level]+d[level];
    
31.         }
    
32.         pos =pos + p[level];
    
33.         temp =str[pos];
    
34.         str[pos] =str[pos+1];
    
35.         str[pos+1] =temp;
    
36.     }while(level>0);
    
37.     return count;
    
38. }
    
39. void main(){
    
40.     long n;
    
41.     n =permute("AB");
    
42.     printf("%d",n);
    
43.     getchar();
    
44. }

复制代码