docker iptables清空:排列与组合的算法实现 - 笔记 - 陈松坚 - CSDN学生大本营 - Powered b...

全排列

目前我所知道的全排列算法有三种，下面一一介绍：

（1）分治算法：这个算法利用了分而治之的思想。我们先从2个数开始，比如说4,5，他们的全排列只有两个45和54。如果在前面加个3,那么全排列就是345,354,也就是3(54)，括号表示里面的数的全排列。当然还有4(35)，5(34)...写到这里，各位看官应该已经看出点门道了吧。三个数的全排列，可以分为三次计算，第一次计算3和(45)的全排列，第二次计算4和(35)的全排列.....也就是说，将序列第一个元素分别与它以及其后的每一个元素代换，得到三个序列，然后对这些序列的除首元素外的子序列进行全排列。思想其实还是挺简单的：

代码实现如下：

1. //input 8 12.61s consumed  
2. //input 8 11.72s consumed remove '-' in the printed array  
3.   
4. #include   
5. #include   
6. #include   
7.   
8. #define LENGTH 27  
9.   
10. int n=0;  
11.   
12. void permute(int[],int,int);  
13. void swapint(int &a,int &b);  
14. void printIntArray (int[],int);  
15.   
16. //Function Implementation  
17.   
18. void swapint(int &a,int &b){  
19.     int temp;  
20.     temp = a;  
21.     a = b;  
22.     b = temp;  
23. }  
24.   
25. void printIntArray(int target[],int length){  
26.     int i;  
27.     for (i=0;i    printf ("\n");  
28. }  
29.   
30.   
31. void permute(int target[],int begin,int end){  
32.       
33.     if (begin==end) {  
34.         printIntArray(target,end+1);  
35.         n++;  
36.         return;  
37.     }  
38.     int i;  
39.     for (i=begin;i<=end;i++){  
40.           
41.         swapint(target[begin],target[i]);  
42.         permute(target,begin+1,end);  
43.         swapint(target[begin],target[i]);  
44.   
45.       
46.     }  
47. }  
48.   
49. //test Functions  
50. void testPermute(){  
51.     int len;  
52.     scanf ("%d",&len);  
53.       
54.     int *testcase =(int *)malloc(len*sizeof(int));  
55.       
56.     int i;  
57.     for (i=0;i    permute(testcase,0,len-1);  
58.   
59. }  
60.   
61. //Main Function  
62. void main(){  
63.     testPermute();  
64.     printf ("n=%d",n);  
65. } 
    

需要注意的是交换了元素，然后进行递归对子序列进行全排列之后，需要将元素的位置换回来。这是为了要还原现场，也就是说递归函数permute的形参target数组在内存中只有一个，递归调用的时候，入栈的只是一个数组指针，递归对子序列进行全排列之后，必定会对原序列造成一定的乱序。因此每次递归之后，都需要还原现场。

当然还有一个方法是将数组放在一个结构体中，而且还不能使用指针哦。参数调用的时候也不能使用引用。这样递归的时候，内存中才会生成新的结构体，当然也有新的数组了。就不会影响其他的操作，不过可想而知，这样写多浪费内存空间，当然也浪费时间。

（2）字典序列算法

字典序列算法是一种非递归算法。而它正是STL中Next_permutation的实现算法。我们来看看他的思路吧：

它的整体思想是让排列成为可递推的数列，也就是说从前一状态的排列，可以推出一种新的状态，直到最终状态。比如说，最初状态是12345，最终状态是54321。其实我觉得这跟我们手动做全排列是一样的。首先是12345，然后12354，然后12435，12453....逐渐地从后往前递增。

看看算法描述：

首先，将待排序列变成有序（升序）序列。

然后，从后向前寻找，找到相邻的两个元素，Ti

接着，如果没有结束，从后向前找到第一个元素Tk，使得Tk>Ti(很多时候k=j)，找到它，交换Ti跟Tk，并且将Tj到Tn(Tn是最后一个元素)的子序列进行倒置操作。输出此序列。并回到第二步继续寻找ij.

算法是很清晰的。看看代码：

1. #include   
2. #include   
3.   
4.   
5. //function definition  
6. void Swap(int &a,int &b);  
7. void Reverse (int[],int,int);  
8. void printArray (int[],int);  
9.   
10. int nextPermutation(int[],int);  
11.   
12.   
13. void Swap(int &a,int &b){  
14.     int tmp;  
15.     tmp=a;  
16.     a=b;  
17.     b=tmp;  
18. }  
19.   
20. void Reverse(int target[],int begin,int end){  
21.       
22.     while (begin        Swap(target[begin],target[end]);  
23.         begin++;  
24.         end--;  
25.     }  
26.   
27. }  
28.   
29. //function implementation  
30. int nextPermutation(int target[],int end){  
31.       
32.     int i,j;  
33.     for (i=end-1;i>=0;i--)   
34.         if (target[i]      
35.     if (i<0) return 0; //means the permutation is over  
36.   
37.     j=i+1;  
38.   
39.     int k;  
40.     for (k=end;target[k]<=target[i];k--);  
41.       
42.     Swap(target[i],target[k]);  
43.     Reverse(target,j,end);  
44.     return 1;  
45. }   
46.   
47. void printArray (int target[],int length){  
48.     int i;  
49.     for (i=0;i    printf ("\n");  
50. }  
51.   
52. //test function  
53. void testPermute(){  
54.     printf ("input a number:");  
55.     int n;  
56.     scanf ("%d",&n);  
57.     int i;  
58.     int * testcase = (int*)malloc(n*sizeof(int));  
59.     for (i=0;i    printArray (testcase,n);  
60.     while (nextPermutation(testcase,n-1)){  
61.         printArray (testcase,n);  
62.     }  
63. }  
64.   
65. //main function  
66. void main(){  
67.   
68.     testPermute();  
69. }  

代码完全按照算法来做，大家应该不难看懂。我就不废话了。

（3）深搜回溯算法

深度搜索，判重，回溯，这个算法应该算是一个基础了。其中八皇后问题是它的经典应用。说实话感觉它就像个万金油一样，在啥地方都能使，但是就是不一定好使就对了。不过还是要实现一下。

 其实细想一下，全排列跟八皇后问题是一样一样的。也是穷举一个数列，只是八皇后对数列的条件跟严格，也即是判重函数不同而已。没有区别的。看看代码：

1. //n=8 Time Consumed 11.78s  
2.   
3. #include   
4. #include   
5.   
6. //function definition  
7. void printArray (const int[],int);  
8. bool isExist(const target[],int);  
9. void permute(int[],const int,int);  
10.   
11.   
12. //function implementation  
13. void printArray(const int target[],int n){  
14.     int i;  
15.     for (i=0;i        printf ("%d",target[i]);  
16.     printf ("\n");  
17. }  
18.   
19. bool isExist(const int target[],int pos){  
20.     if (pos==0) return false;  
21.     int i;  
22.     for (i=0;i        if (target[i]==target[pos]) return true;  
23.       
24.     return false;  
25.   
26. }  
27.   
28. void permute (int target[],const int n,int i){  
29.       
30.     if (i==n) {  
31.         printArray(target,n);  
32.         return;  
33.     }  
34.   
35.     for (target[i]=1;target[i]<=n;target[i]++)  
36.         if (isExist(target,i) == false) permute(target,n,i+1);  
37.   
38.     //target[i]=1;  
39.     return;  
40.   
41. }  
42. //test functions  
43. void testPermutation(){  
44.       
45.     int n;  
46.     printf ("Input a Number:");  
47.     scanf ("%d",&n);  
48.     int * testcase=(int*)malloc(n*sizeof(int));  
49.     int i;  
50.     for (i=0;i  
51.     permute(testcase,n,0);  
52. }  
53. //main function  
54. void main(){  
55.     testPermutation();    
56. }  

注意，我在递归函数permute中，回溯甚至没有将当时位置上的数消掉。看被注释掉的target[i]=1。而是直接在for循环中添加初始语句target[i]=1。这就表示说只要进行深一步搜索，都先将下一位置的数初始化掉。这样就不用在回溯时对当前位置的错误值进行处理了。更加简化了。

再看看非递归版的，也就是使用堆栈的形式：

1. // when n=8 time consumed 11.77s  
2. #include   
3. #include   
4.   
5. //function definition  
6. void permute(int [],int);  
7. void printArray(const int[],const int);  
8. bool isExist(const int[],const int);  
9.   
10.   
11.   
12. //function implementation  
13. void printArray(const int target[],const int n){  
14.     int i;  
15.     for (i=0;i        printf ("%d",target[i]);  
16.     printf ("\n");  
17. }  
18.   
19. bool isExist(const int target[],int pos){  
20.     if (pos==0) return false;  
21.   
22.     int i;  
23.     for (i=0;i        if (target[i]==target[pos]) return true;  
24.     return false;  
25. }  
26.   
27. void permute(int stack[],int n){  
28.       
29.     int sp=0;   //stack pointer  
30.     while (sp>=0) {  
31.           
32.         stack[sp]++;  
33.         while (stack[sp]<=n && isExist(stack,sp)==true ) stack[sp]++;  
34.   
35.         if (stack[sp]<=n) {  
36.             //when stack is full,output the result  
37.             //and then backtrack  
38.             if (sp==n-1) {  
39.                 printArray(stack,n);  
40.                 sp--;  
41.             }  
42.             else {  
43.             //push stack, which means search foward  
44.                 sp++;  
45.                 stack[sp]=0;  
46.             }  
47.         }  
48.         else {  
49.         //backtrack  
50.             sp--;  
51.         }  
52.     }  
53.     return;  
54. }  
55.   
56. //test function  
57. void testPermutation(){  
58.       
59.     int n;  
60.     printf ("Input a Number:");  
61.     scanf ("%d",&n);  
62.   
63.     int i;  
64.     int * testcase=(int*)malloc(n*sizeof(int));  
65.     for (i=0;i    permute(testcase,n);  
66.   
67. }  
68. //main function  
69. void main(){  
70.     testPermutation();  
71. }  

非递归形式算法思想是一样的，不过就是需要自己来维护一个堆栈。注意在循环中，需要首先对堆栈元素进行自加操作，不然的话，回溯之后，就不会改变堆栈值，而使程序陷入死循环。不过当然，你要使用do while来代替这种写法，那当然也是没有问题的。

我只是想说，只要是递归形式的算法，都可以用堆栈来实现非递归的形式。大家不妨来探讨一下这个一一对应的转换的具体形式。

组合

关于组合，我有一个比较帅的算法，在这里跟大家分享一下。呵呵。

这是非递归的算法，我感觉跟全排列的字典序列算法思想上比较像。

你看它是怎么实现的：

求n个数中的m个数的组合。

首先，初始化一个n个元素的数组（全部由0，1组成），将前m个初始化为1，后面的为0。这时候就可以输出第一个组合了。为1的元素的下标所对应的数。

算法开始：从前往后找，找到第一个10组合，将其反转成01，然后将其前面的所有1，全部往左边推，即保证其前面的1都在最左边。然后就可以按照这个01序列来输出一个组合结果了。

而如果找不到10组合，就表示说所有情况都输出了，为什么？你想，（以n=5,m=3为例）一开始是11100，最后就是00111，已经没有10组合了。

这种将问题转换为01序列（也就是真假序列）的想法值得我们考虑和借鉴。

最后看看实现代码：

1. #include   
2. #include   
3. #include   
4.   
5. int l=0;  
6.   
7. //function definition  
8. void composition(const char [],int,int);   
9. void printCompostion(const char[],const bool[],int);  
10.   
11. //function implementation  
12. void printCompostion(const char source[],const bool comp[],int n){  
13.     int i;  
14.     for (i=0;i        if (comp[i]==true) printf ("%c-",source[i]);  
15.     printf ("\n");  
16.   
17. }  
18.   
19. void compostion(const char* source,int n,int m){  
20.       
21.     bool * comp = (bool*)malloc(n*sizeof(bool));  
22.       
23.     int i;  
24.     for (i=0;i    for (i=m;i  
25.     printCompostion(source,comp,n);  
26.     l++;  
27.   
28.     while(true){  
29.           
30.         for (i=0;i            if (comp[i]==true&&comp[i+1]==false) break;  
31.           
32.         if (i==n-1) return;  //all the compostion is found out  
33.           
34.         comp[i]=false;  
35.         comp[i+1]=true;  
36.           
37.         int p=0;  
38.         while (p            while (comp[p]==true) p++;  
39.             while (comp[i]==false) i--;  
40.             if (p                comp[p]=true;  
41.                 comp[i]=false;  
42.             }  
43.         }  
44.         printCompostion(source,comp,n);  
45.         l++;  
46.     }  
47. }  
48.   
49.   
50. //test function  
51. void testCompostion(){  
52.       
53.     char* testcase = "abcdefghijklmno";  
54.     int n=strlen(testcase);  
55.     int m=7;  
56.     compostion(testcase,n,m);  
57. }  
58.   
59. //main function  
60. void main(){  
61.     testCompostion();  
62.     printf ("total=%d\n",l);  
63. }  

01序列我是用bool类型来实现的。尽可能地少占用内存吧。而在实现将1往左移的步骤时，我是采用了将左边的0跟右边的1相调换的思想。

关于组合大家如果有更好的方法，不妨跟贴讨论哦。