排列：從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)。
[cpp]
#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]++;
/*保存當前搜索到的第i個元素*/
p[pos] = i;
/*遞歸搜索*/
permute(pos+1,n,r);
/*恢復遞歸前的值，目的是使以後改元素可用*/
used[i]--;
}
}
}
//從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]++;
/*搜索第i+1個元素*/
combine(pos+1,i+1,n,r);
/*恢復遞歸前的值*/
used[i]--;
}
}
}
//產生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);
}
int main()
{
strcpy(s,"ABCD");
int n = 4;
int r = 4;
//permute(0,n,r);
//combine(0,0,n,r);
//binary_sequence(0,r);
cout<<"string: "<<s<<endl;
all_combine(0,r);
return 0;
}
另一個排列算法的實現：
算法perm(a,k,m)遞歸產生所有前綴是a[0:k-1]，後綴是a[k:m]的全排列的所有排列。
函數調用perm(a,0,n-1)則產生a[0:n-1]的全排列。
k<m，算法將a[k:m]中的每一個元素分別與a[k]交換，然後遞歸計算a[k+1:m]的全排列，並將計算結果作為a[0:k]的後綴。
[cpp]
template <class Type>
void perm(Type a[], int k, int m)
{
if(k==m)
{
for(int i=0; i<=m; ++i)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
else
for(int i=k; i<=m; ++i)
{
swap(a[i],a[k]);
perm(a,k+1,m);
swap(a[i],a[k]);
}
} www.2cto.com
作者：luxiaoxun
