排列：从n个不同元素中，任取m(m<=n)个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(m<=n)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号A(n,m)表示。 A(n,m)=n(n-1)(n-2)……(n-m+1)= n!/(n-m)! 此外规定0!=1
组合：从n个不同元素中，任取m(m<=n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m<=n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。用符号C(n,m) 表示。 C(n,m)=A(n,m)/m!=n!/((n-m)!*m!)； C(n,m)=C(n,n-m)。
C语言使用标志位实现
#include <iostream> using namespace std; #define MaxN 10 char used[MaxN]; int p[MaxN]; char s[MaxN]; //从n个元素中选r个进行排列 void permute(int pos,const int n,const int r) { int i; /*如果已是第r个元素了，则可打印r个元素的排列 */ if(pos == r) { for(i=0; i<r; i++) cout<<s[p[i]]; cout<<endl; return; } for (i=0; i<n; i++) { if(!used[i]) { /*如果第i个元素未用过*/ /*使用第i个元素，作上已用标记，目的是使以后该元素不可用*/ used[i] = 1; /*保存当前搜索到的第i个元素*/ p[pos] = i; /*递归搜索*/ permute(pos+1,n,r); /*恢复递归前的值，目的是使以后改元素可用*/ used[i] = 0; } } } //从n个元素中选r个进行组合 void combine(int pos,int h,const int n,const int r) { int i; /*如果已选了r个元素了，则打印它们*/ if (pos == r) { for(i=0; i<r; i++) cout<<s[p[i]]; cout<<endl; return; } for(i=h; i<=n-r+pos; i++) /*对于所有未用的元素*/ { if (!used[i]) { /*把它放置在组合中*/ p[pos] = i; /*使用该元素*/ used[i] = 1; /*搜索第i+1个元素*/ combine(pos+1,i+1,n,r); /*恢复递归前的值*/ used[i] = 0; } } } //产生0~2^r-1的二进制序列 void binary_sequence(int pos,const int r) { int i; if(pos == r) { for(i=0; i<r; i++) cout<<p[i]; cout<<endl; return; } p[pos] = 0; binary_sequence(pos+1,r); p[pos] = 1; binary_sequence(pos+1,r); } //利用上面的二进制序列打印字符串的所有组合 //如"abc"输出a、b、c、ab、ac、bc、abc。 void all_combine(int pos,const int r) { int i; if(pos == r) { for(i=0; i<r; i++) { if(p[i]==1) cout<<s[i]; } cout<<endl; return; } p[pos] = 0; all_combine(pos+1,r); p[pos] = 1; all_combine(pos+1,r); } //利用r进制序列打印字符串的所有重复组合 //如"abc"输出aaa、aab、aac、aba、abb、abc、aca、acb、acc...。 void repeative_combine(int pos,const int r) { int i; if(pos == r) { for(i=0; i<r; i++) { cout<<s[p[i]]; } cout<<endl; return; } for(i=0; i<r; ++i) { p[pos] = i; repeative_combine(pos+1,r); } } int main() { strcpy(s,"ABC"); int n = 3; int r = 3; //permute(0,n,r); //combine(0,0,n,r); //binary_sequence(0,r); //cout<<"string: "<<s<<endl; //all_combine(0,r); //repeative_combine(0,r); return 0; }
排列组合算法的递归实现：
#include <iostream> using namespace std; template <class Type> void permute(Type a[], int start, int end) { if(start == end) { for(int i = 0; i <= end; ++i) { cout<<a[i]<<" "; } cout<<endl; } else { for(int i = start; i <= end; ++i) { swap(a[i],a[start]); permute(a,start+1,end); swap(a[i],a[start]); } } } template <class Type> void combine(Type a[], bool b[], int start, int end) { if(start > end) { for(int i = 0; i <= end; ++i) { if(b[i]) cout<<a[i]<<" "; } cout<<endl; } else { b[start] = true; combine(a,b,start+1,end); b[start] = false; combine(a,b,start+1,end); } } int main() { int p[3]={1,2,3}; int N = 3; cout<<"permute:"<<endl; permute(p,0,N-1); cout<<"combine:"<<endl; bool b[3]; combine(p,b,0,N-1); return 0; }
排列算法的迭代实现
C++ STL中提供了next_permutation和prev_permutation算法。因为next_permutation和prev_permutation实际上是一样的，因此只描述next_permutation算法。next_permutation()函数的作用是取下一个排列组合。考虑{a，b，c}的全排列：abc，acb，bac，bca，cab，cba，以“bac”作为参考，那么next_permutation()所得到的下一个排列组合是bca，prev_permutation()所得到的前一个排列组合是“acb”，之于“前一个”和“后一个”，是按字典进行排序的。
next_permutation()算法描述：
- 从str的尾端开始逆着寻找相邻的元素，*i和*ii，满足*i<*ii；
- 接着，又从str的尾端开始逆着寻找一元素，*j，满足*i>*j（*i从步骤一中得到）；
- swap(*i,*j)；
- 将*ii之后（包括*ii）的所有元素逆转。
举个例子，需要找到“01324”的下一个排列，找到*i=2，*ii=4，*j=4，下一个排列即“01342”。再来找到“abfedc”的下一个排列，找到*i=b，*ii=f，*j=c，swap操作过后为“acfedb”，逆转操作过后为“acbdef”。
//求阶乘 int factorial(int n) { if(n == 1) return 1; return n*factorial(n-1); } template <class Type> void print(Type a, int n) { for(int i = 0; i < n; ++i) cout<<a[i]<<" "; cout<<endl; } template <class Type> void perm2(Type a, int n) { int i,ii,j; int cnt = 1; print(a,n); int num = factorial(n); // STL <algorithm> next_permutation()函数的核心算法 while(++cnt <= num) { i = n - 2; ii = n - 1; j = ii; while(a[i] >= a[ii]) --i,--ii; //find *i and *ii while(a[i] >= a[j]) --j; //find *j swap(a[i],a[j]); //STL swap reverse(a+ii,a+n); //STL reverse print(a,n); } }