任意排列、组合算法终极Shell脚本

xrzs1986

顶！！！！

crulat

代码已优化，现在速度已经非常快了！

cjaizss

crulat 发表于 2012-06-20 03:31
Invoke the script:
C 4 3P 4 3C 8 5P 5 5

呵呵

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. int *flag;
   
5. void print(int*a,int num)
   
6. {
   
7.         int i;
   
8.         num--;
   
9.         for(i=0;i<num;i++)
   
10.                 printf("%d->",a[i]);
    
11.         printf("%d\n",a[num]);
    
12. }
    
13. 
    
14. int next(int*a,int m, int n,int how)
    
15. {
    
16.         int i,j,k,x;
    
17.         if(how) {
    
18.                 for(j=n-1;j>=0;j--) {
    
19.                         for(i=a[j];i<m;i++)
    
20.                                 if(flag[i]==0)
    
21.                                         break;
    
22.                         if(i<m) {
    
23.                                 flag[a[j]-1]=0;
    
24.                                 a[j]=i+1;
    
25.                                 flag[i]=1;
    
26. 
    
27.                                 for(x=0,k=j+1;k<n;k++) {
    
28.                                         while(flag[x]==1)x++;
    
29.                                         a[k]=x+1;
    
30.                                         flag[x]=1;
    
31.                                 }
    
32.                                 return 0;
    
33.                         }
    
34.                         flag[a[j]-1]=0;
    
35.                 }
    
36.         }
    
37.         else {
    
38.                 if(a[n-1]<m) {
    
39.                         a[n-1]++;
    
40.                         return 0;
    
41.                 }
    
42.                 for(i=n-1;i>0;i--)
    
43.                         if(a[i]>a[i-1]+1)
    
44.                                 break;
    
45.                 if(i>0) {
    
46.                         a[i-1]++;
    
47.                         for(;i<n;i++)
    
48.                                 a[i]=a[i-1]+1;
    
49.                         return 0;
    
50.                 }
    
51.         }
    
52.         return 1;
    
53. }
    
54. 
    
55. int main(int argc,char**argv)
    
56. {
    
57.         int *a,i;
    
58.         char c;
    
59.         int m,n;
    
60.         int how=0;
    
61.         c=argv[3][0];
    
62.         sscanf(argv[1],"%d",&m);
    
63.         sscanf(argv[2],"%d",&n);
    
64.         if(!(0<n&&n<=m)||(c!='P'&&c!='p'&&c!='C'&&c!='c'))
    
65.                 return 1;
    
66.         a = malloc(sizeof(int)*n);
    
67.         if(c=='P'||c=='p') {
    
68.                 how =1;
    
69.                 flag = malloc(sizeof(int)*m);
    
70.                 for(i=0;i<n;i++)
    
71.                         flag[i]=1;
    
72.                 for(;i<m;i++)
    
73.                         flag[i]=0;
    
74.         }
    
75.         if(a==NULL)
    
76.                 return 1;
    
77.         for(i=0;i<n;i++)
    
78.                 a[i]=i+1;
    
79.         while(1) {
    
80.                 print(a,n);
    
81.                 if(next(a,m,n,how))
    
82.                         return 0;
    
83.         }
    
84. }
    
85. 
    

复制代码

没有递归,只有迭代

1. 
   
2. linux-p94b:~ # ./a.out 4 3 c
   
3. 1->2->3
   
4. 1->2->4
   
5. 1->3->4
   
6. 2->3->4
   
7. linux-p94b:~ # ./a.out 4 3 p | xargs -n 6
   
8. 1->2->3 1->2->4 1->3->2 1->3->4 1->4->2 1->4->3
   
9. 2->1->3 2->1->4 2->3->1 2->3->4 2->4->1 2->4->3
   
10. 3->1->2 3->1->4 3->2->1 3->2->4 3->4->1 3->4->2
    
11. 4->1->2 4->1->3 4->2->1 4->2->3 4->3->1 4->3->2
    
12. linux-p94b:~ # ./a.out 8 5 c | xargs -n 8
    
13. 1->2->3->4->5 1->2->3->4->6 1->2->3->4->7 1->2->3->4->8 1->2->3->5->6 1->2->3->5->7 1->2->3->5->8 1->2->3->6->7
    
14. 1->2->3->6->8 1->2->3->7->8 1->2->4->5->6 1->2->4->5->7 1->2->4->5->8 1->2->4->6->7 1->2->4->6->8 1->2->4->7->8
    
15. 1->2->5->6->7 1->2->5->6->8 1->2->5->7->8 1->2->6->7->8 1->3->4->5->6 1->3->4->5->7 1->3->4->5->8 1->3->4->6->7
    
16. 1->3->4->6->8 1->3->4->7->8 1->3->5->6->7 1->3->5->6->8 1->3->5->7->8 1->3->6->7->8 1->4->5->6->7 1->4->5->6->8
    
17. 1->4->5->7->8 1->4->6->7->8 1->5->6->7->8 2->3->4->5->6 2->3->4->5->7 2->3->4->5->8 2->3->4->6->7 2->3->4->6->8
    
18. 2->3->4->7->8 2->3->5->6->7 2->3->5->6->8 2->3->5->7->8 2->3->6->7->8 2->4->5->6->7 2->4->5->6->8 2->4->5->7->8
    
19. 2->4->6->7->8 2->5->6->7->8 3->4->5->6->7 3->4->5->6->8 3->4->5->7->8 3->4->6->7->8 3->5->6->7->8 4->5->6->7->8
    
20. linux-p94b:~ # ./a.out 5 5 p | xargs -n 12
    
21. 1->2->3->4->5 1->2->3->5->4 1->2->4->3->5 1->2->4->5->3 1->2->5->3->4 1->2->5->4->3 1->3->2->4->5 1->3->2->5->4 1->3->4->2->5 1->3->4->5->2 1->3->5->2->4 1->3->5->4->2
    
22. 1->4->2->3->5 1->4->2->5->3 1->4->3->2->5 1->4->3->5->2 1->4->5->2->3 1->4->5->3->2 1->5->2->3->4 1->5->2->4->3 1->5->3->2->4 1->5->3->4->2 1->5->4->2->3 1->5->4->3->2
    
23. 2->1->3->4->5 2->1->3->5->4 2->1->4->3->5 2->1->4->5->3 2->1->5->3->4 2->1->5->4->3 2->3->1->4->5 2->3->1->5->4 2->3->4->1->5 2->3->4->5->1 2->3->5->1->4 2->3->5->4->1
    
24. 2->4->1->3->5 2->4->1->5->3 2->4->3->1->5 2->4->3->5->1 2->4->5->1->3 2->4->5->3->1 2->5->1->3->4 2->5->1->4->3 2->5->3->1->4 2->5->3->4->1 2->5->4->1->3 2->5->4->3->1
    
25. 3->1->2->4->5 3->1->2->5->4 3->1->4->2->5 3->1->4->5->2 3->1->5->2->4 3->1->5->4->2 3->2->1->4->5 3->2->1->5->4 3->2->4->1->5 3->2->4->5->1 3->2->5->1->4 3->2->5->4->1
    
26. 3->4->1->2->5 3->4->1->5->2 3->4->2->1->5 3->4->2->5->1 3->4->5->1->2 3->4->5->2->1 3->5->1->2->4 3->5->1->4->2 3->5->2->1->4 3->5->2->4->1 3->5->4->1->2 3->5->4->2->1
    
27. 4->1->2->3->5 4->1->2->5->3 4->1->3->2->5 4->1->3->5->2 4->1->5->2->3 4->1->5->3->2 4->2->1->3->5 4->2->1->5->3 4->2->3->1->5 4->2->3->5->1 4->2->5->1->3 4->2->5->3->1
    
28. 4->3->1->2->5 4->3->1->5->2 4->3->2->1->5 4->3->2->5->1 4->3->5->1->2 4->3->5->2->1 4->5->1->2->3 4->5->1->3->2 4->5->2->1->3 4->5->2->3->1 4->5->3->1->2 4->5->3->2->1
    
29. 5->1->2->3->4 5->1->2->4->3 5->1->3->2->4 5->1->3->4->2 5->1->4->2->3 5->1->4->3->2 5->2->1->3->4 5->2->1->4->3 5->2->3->1->4 5->2->3->4->1 5->2->4->1->3 5->2->4->3->1
    
30. 5->3->1->2->4 5->3->1->4->2 5->3->2->1->4 5->3->2->4->1 5->3->4->1->2 5->3->4->2->1 5->4->1->2->3 5->4->1->3->2 5->4->2->1->3 5->4->2->3->1 5->4->3->1->2 5->4->3->2->1
    
31. linux-p94b:~ #
    
32. 
    

复制代码

crulat

回复 13# cjaizss

佩服，佩服！
大一统的方法，果断收藏，学习了！
   

dahaoshanhe

楼上各位都好强，自惭形秽呀~~~  学习中~~~

zhanglong71

有意思！mark一下。

kkkkk1530

永夜····牛啊

aqbssh

回复 13# cjaizss


    果然牛帖，

aqbssh

回复 1# crulat


    我在想，如果要排列的元素在一个文件中，该怎么实现呢？