浅谈c语言中一种典型的排列组合算法

2020-01-26 14:09:06

字体：大中小

来源：转载

供稿：网友

c语言中的全排列算法和组合数算法在实际问题中应用非常之广，但算法有许许多多，而我个人认为方法不必记太多，最好只记熟一种即可，一招鲜亦可吃遍天

全排列：

#include<stdio.h>void swap(int *p1,int *p2){int t=*p1;*p1=*p2;*p2=t;}void permutation(int a[],int index,int size){if(index==size){for(int i=0;i<size;i++)printf("%d ",a[i]);printf("/n");}else{for(int j=index;j<size;j++){swap(&a[j],&a[index]);permutation(a,index+1,size);//此处用到递归思想swap(&a[j],&a[index]);}}}int main(){int n;scanf("%d",&n);int a[n];for(int i=0;i<n;i++)a[i]=i+1;permutation(a,0,n);return 0;}

组合：

#include<stdio.h>void combine(int n,int m,int a[],int b[],const int M){for(int j=n;j>=m;j--){b[m-1]=j-1;if(m>1)combine(j-1,m-1,a,b,M);//用到了递归思想else{for(int i=M-1;i>=0;i--)printf("%d ",a[b[i]]);printf("/n");}}}int main(){int n,m;scanf("%d%d",&n,&m);int a[n];int b[m];for(int i=0;i<n;i++)a[i]=i+1;const int M=m;combine(n,m,a,b,M);}