排列组合算法-阿里云开发者社区

开发者社区> ghost丶桃子> 正文

排列组合算法

简介:
+关注继续查看

    排列:从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_permutationprev_permutation算法。因为next_permutationprev_permutation实际上是一样的,因此只描述next_permutation算法。next_permutation()函数的作用是取下一个排列组合。考虑{a,b,c}的全排列:abc,acb,bac,bca,cab,cba,以“bac”作为参考,那么next_permutation()所得到的下一个排列组合是bca,prev_permutation()所得到的前一个排列组合是“acb”,之于“前一个”和“后一个”,是按字典进行排序的。

next_permutation()算法描述:

  1. 从str的尾端开始逆着寻找相邻的元素,*i和*ii,满足*i<*ii;
  2. 接着,又从str的尾端开始逆着寻找一元素,*j,满足*i>*j(*i从步骤一中得到);
  3. swap(*i,*j);
  4. 将*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);
    }
}
复制代码

 

作者:阿凡卢
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。
http://www.cnblogs.com/luxiaoxun/archive/2012/08/08/2628153.html

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Java实现全排列、组合算法
Java实现全排列、组合算法
9437 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
9946 0
排序算法(七):快速排序
快速排序是通过分治的方式,根据选定元素将待排序集合拆分为两个值域的子集合,并对子集合递归拆分,当拆分后的每个子集合中元素个数为一时,自然就是有序状态。
726 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
10878 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13692 0
1955
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载