当前位置:编程学习 > C/C++ >>

排列组合问题

排列:从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]); <

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,