排列与组合的算法实现 - 笔记 - 陈松坚 - CSDN学生大本营 - Powered b...
由于老师提出了全排列问题。我心血来潮,将组合也弄了一下。现在写篇日志记录一下。
全排列目前我所知道的全排列算法有三种,下面一一介绍:
(1)分治算法:这个算法利用了分而治之的思想。我们先从2个数开始,比如说4,5,他们的全排列只有两个45和54。如果在前面加个3,那么全排列就是345,354,也就是3(54),括号表示里面的数的全排列。当然还有4(35),5(34)...写到这里,各位看官应该已经看出点门道了吧。三个数的全排列,可以分为三次计算,第一次计算3和(45)的全排列,第二次计算4和(35)的全排列.....也就是说,将序列第一个元素分别与它以及其后的每一个元素代换,得到三个序列,然后对这些序列的除首元素外的子序列进行全排列。思想其实还是挺简单的:代码实现如下:
-
-
-
- #include <stdio.h>
- #include <string.h>
- #include <stdlib.h>
-
- #define LENGTH 27
-
- int n=0;
-
- void permute(int[],int,int);
- void swapint(int &a,int &b);
- void printIntArray (int[],int);
-
-
-
- void swapint(int &a,int &b){
- int temp;
- temp = a;
- a = b;
- b = temp;
- }
-
- void printIntArray(int target[],int length){
- int i;
- for (i=0;i<length;i++) printf ("%d",target[i]);
- printf ("\n");
- }
-
-
- void permute(int target[],int begin,int end){
-
- if (begin==end) {
-
- n++;
- return;
- }
- int i;
- for (i=begin;i<=end;i++){
-
- swapint(target[begin],target[i]);
- permute(target,begin+1,end);
- swapint(target[begin],target[i]);
-
-
- }
- }
-
-
- void testPermute(){
- int len;
- scanf ("%d",&len);
-
- int *testcase =(int *)malloc(len*sizeof(int));
-
- int i;
- for (i=0;i<len;i++) testcase[i]=i+1;
- permute(testcase,0,len-1);
-
- }
-
-
- void main(){
- testPermute();
- printf ("n=%d",n);
- }
需要注意的是交换了元素,然后进行递归对子序列进行全排列之后,需要将元素的位置换回来。这是为了要还原现场,也就是说递归函数permute的形参target数组在内存中只有一个,递归调用的时候,入栈的只是一个数组指针,递归对子序列进行全排列之后,必定会对原序列造成一定的乱序。因此每次递归之后,都需要还原现场。
当然还有一个方法是将数组放在一个结构体中,而且还不能使用指针哦。参数调用的时候也不能使用引用。这样递归的时候,内存中才会生成新的结构体,当然也有新的数组了。就不会影响其他的操作,不过可想而知,这样写多浪费内存空间,当然也浪费时间。
(2)字典序列算法
字典序列算法是一种非递归算法。而它正是STL中Next_permutation的实现算法。我们来看看他的思路吧:
它的整体思想是让排列成为可递推的数列,也就是说从前一状态的排列,可以推出一种新的状态,直到最终状态。比如说,最初状态是12345,最终状态是54321。其实我觉得这跟我们手动做全排列是一样的。首先是12345,然后12354,然后12435,12453....逐渐地从后往前递增。看看算法描述:
首先,将待排序列变成有序(升序)序列。
然后,从后向前寻找,找到相邻的两个元素,Ti<Tj,(j=i+1)。如果没有找到,则说明整个序列已经是降序排列了,也就是说到达最终状态54321了。此时,全排列结束。
接着,如果没有结束,从后向前找到第一个元素Tk,使得Tk>Ti(很多时候k=j),找到它,交换Ti跟Tk,并且将Tj到Tn(Tn是最后一个元素)的子序列进行倒置操作。输出此序列。并回到第二步继续寻找ij.
算法是很清晰的。看看代码:
- #include <stdio.h>
- #include <stdlib.h>
-
-
-
- void Swap(int &a,int &b);
- void Reverse (int[],int,int);
- void printArray (int[],int);
-
- int nextPermutation(int[],int);
-
-
- void Swap(int &a,int &b){
- int tmp;
- tmp=a;
- a=b;
- b=tmp;
- }
-
- void Reverse(int target[],int begin,int end){
-
- while (begin<end){
- Swap(target[begin],target[end]);
- begin++;
- end--;
- }
-
- }
-
-
- int nextPermutation(int target[],int end){
-
- int i,j;
- for (i=end-1;i>=0;i--)
- if (target[i]<target[i+1]) break;
-
- if (i<0) return 0;
-
- j=i+1;
-
- int k;
- for (k=end;target[k]<=target[i];k--);
-
- Swap(target[i],target[k]);
- Reverse(target,j,end);
- return 1;
- }
-
- void printArray (int target[],int length){
- int i;
- for (i=0;i<length;i++) printf ("%d-",target[i]);
- printf ("\n");
- }
-
-
- void testPermute(){
- printf ("input a number:");
- int n;
- scanf ("%d",&n);
- int i;
- int * testcase = (int*)malloc(n*sizeof(int));
- for (i=0;i<n;i++) testcase[i]=i+1;
- printArray (testcase,n);
- while (nextPermutation(testcase,n-1)){
- printArray (testcase,n);
- }
- }
-
-
- void main(){
-
- testPermute();
- }
代码完全按照算法来做,大家应该不难看懂。我就不废话了。(3)深搜回溯算法
深度搜索,判重,回溯,这个算法应该算是一个基础了。其中八皇后问题是它的经典应用。说实话感觉它就像个万金油一样,在啥地方都能使,但是就是不一定好使就对了。不过还是要实现一下。
其实细想一下,全排列跟八皇后问题是一样一样的。也是穷举一个数列,只是八皇后对数列的条件跟严格,也即是判重函数不同而已。没有区别的。看看代码:
-
-
- #include <stdio.h>
- #include <stdlib.h>
-
-
- void printArray (const int[],int);
- bool isExist(const target[],int);
- void permute(int[],const int,int);
-
-
-
- void printArray(const int target[],int n){
- int i;
- for (i=0;i<n;i++)
- printf ("%d",target[i]);
- printf ("\n");
- }
-
- bool isExist(const int target[],int pos){
- if (pos==0) return false;
- int i;
- for (i=0;i<pos;i++)
- if (target[i]==target[pos]) return true;
-
- return false;
-
- }
-
- void permute (int target[],const int n,int i){
-
- if (i==n) {
- printArray(target,n);
- return;
- }
-
- for (target[i]=1;target[i]<=n;target[i]++)
- if (isExist(target,i) == false) permute(target,n,i+1);
-
-
- return;
-
- }
-
- void testPermutation(){
-
- int n;
- printf ("Input a Number:");
- scanf ("%d",&n);
- int * testcase=(int*)malloc(n*sizeof(int));
- int i;
- for (i=0;i<n;i++) testcase[i]=1;
-
- permute(testcase,n,0);
- }
-
- void main(){
- testPermutation();
- }
注意,我在递归函数permute中,回溯甚至没有将当时位置上的数消掉。看被注释掉的target[i]=1。而是直接在for循环中添加初始语句target[i]=1。这就表示说只要进行深一步搜索,都先将下一位置的数初始化掉。这样就不用在回溯时对当前位置的错误值进行处理了。更加简化了。再看看非递归版的,也就是使用堆栈的形式:
-
- #include <stdio.h>
- #include <stdlib.h>
-
-
- void permute(int [],int);
- void printArray(const int[],const int);
- bool isExist(const int[],const int);
-
-
-
-
- void printArray(const int target[],const int n){
- int i;
- for (i=0;i<n;i++)
- printf ("%d",target[i]);
- printf ("\n");
- }
-
- bool isExist(const int target[],int pos){
- if (pos==0) return false;
-
- int i;
- for (i=0;i<pos;i++)
- if (target[i]==target[pos]) return true;
- return false;
- }
-
- void permute(int stack[],int n){
-
- int sp=0;
- while (sp>=0) {
-
- stack[sp]++;
- while (stack[sp]<=n && isExist(stack,sp)==true ) stack[sp]++;
-
- if (stack[sp]<=n) {
-
-
- if (sp==n-1) {
- printArray(stack,n);
- sp--;
- }
- else {
-
- sp++;
- stack[sp]=0;
- }
- }
- else {
-
- sp--;
- }
- }
- return;
- }
-
-
- void testPermutation(){
-
- int n;
- printf ("Input a Number:");
- scanf ("%d",&n);
-
- int i;
- int * testcase=(int*)malloc(n*sizeof(int));
- for (i=0;i<n;i++) testcase[i]=0;
- permute(testcase,n);
-
- }
-
- void main(){
- testPermutation();
- }
非递归形式算法思想是一样的,不过就是需要自己来维护一个堆栈。注意在循环中,需要首先对堆栈元素进行自加操作,不然的话,回溯之后,就不会改变堆栈值,而使程序陷入死循环。不过当然,你要使用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序列(也就是真假序列)的想法值得我们考虑和借鉴。
最后看看实现代码:
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
-
- int l=0;
-
-
- void composition(const char [],int,int);
- void printCompostion(const char[],const bool[],int);
-
-
- void printCompostion(const char source[],const bool comp[],int n){
- int i;
- for (i=0;i<n;i++)
- if (comp[i]==true) printf ("%c-",source[i]);
- printf ("\n");
-
- }
-
- void compostion(const char* source,int n,int m){
-
- bool * comp = (bool*)malloc(n*sizeof(bool));
-
- int i;
- for (i=0;i<m;i++) comp[i]=true;
- for (i=m;i<n;i++) comp[i]=false;
-
- printCompostion(source,comp,n);
- l++;
-
- while(true){
-
- for (i=0;i<n-1;i++)
- if (comp[i]==true&&comp[i+1]==false) break;
-
- if (i==n-1) return;
-
- comp[i]=false;
- comp[i+1]=true;
-
- int p=0;
- while (p<i){
- while (comp[p]==true) p++;
- while (comp[i]==false) i--;
- if (p<i) {
- comp[p]=true;
- comp[i]=false;
- }
- }
- printCompostion(source,comp,n);
- l++;
- }
- }
-
-
-
- void testCompostion(){
-
- char* testcase = "abcdefghijklmno";
- int n=strlen(testcase);
- int m=7;
- compostion(testcase,n,m);
- }
-
-
- void main(){
- testCompostion();
- printf ("total=%d\n",l);
- }
01序列我是用bool类型来实现的。尽可能地少占用内存吧。而在实现将1往左移的步骤时,我是采用了将左边的0跟右边的1相调换的思想。关于组合大家如果有更好的方法,不妨跟贴讨论哦。
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报。