排列组合

排列

全排列是将一组数按一定顺序进行排列，如果这组数有n个，那么全排列数为n!个。现以{1, 2, 3}为例说明如何编写全排列的递归算法

第一层S1表示第一个数分别与第1、2、3个数交换位置，如123是1和第一个数1交换，213是1和第二个数2交换，321是1和第三个数交换

第二层S2是第二个数分别与第2、3个数交换位置。则最后一层的所有叶子节点，即为全排列的所有结果。第k层中的节点Sk就是父节点中的第k个数，分别与第k、k+1...n个数交换位置。

也可用stl的next_permutation()和perv_permutation()

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

template <class T>
class Perm
{
    public:
        //由于vector本身就是模板,在其模板参数未确定之前,也就是具体类型没有确定之前,这个T是未知的
        //typename就是告诉编译器先不管具体类型，等模板实例化的时候再确定 
        void perm(vector<T> &a,typename vector<T>::iterator begin);
        bool is_swap(typename vector<T>::iterator i,typename vector<T>::iterator j);
    private:
        static int i;
};
template <class T>
int Perm<T>::i=0;

template <class T>
bool Perm<T>::is_swap(typename vector<T>::iterator i,typename vector<T>::iterator j)
{    
    for(typename vector<T>::iterator k=i;k!=j;++k)
        if(*k==*j)
            return false;
    return true;
    
}

template <class T>
void Perm<T>::perm(vector<T> &a,typename vector<T>::iterator begin)
{
    if(begin==a.end())
    {
        cout<<" 第"<<++i<<" 个排列为:";
        for_each(a.begin(),a.end(),[](int i)
            {
                cout<<i<<" ";
            });
        cout<<endl;
    }
    for(auto i=begin;i!=a.end();++i)
    {
        if(!is_swap(begin,i))
            continue;
        swap(*begin,*i);
        perm(a,begin+1);
        swap(*begin,*i);
    }
}

int main()
{
    vector<int> a;
    int n;
    cout<<" 请输入元素的个数:"<<endl;
    cin>>n;
    for(int i=0;i<n;++i)
    {
        int t;
        cin>>t;
        a.push_back(t);
    }
    
    Perm<int> p;
    p.perm(a,a.begin());
    return 0;
}

组合

第一层S1中的节点是数组中的所有数字，第二次S2中的节点是分别从父节点的下一个位置开始。因为这个例子中m=2，所以共有2层。从第一层到第二层，深度遍历这颗树，即可得到所有组合。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

template <class T> 
class Combine
{
    public:
        void combine(vector<T> a,int begin,int num);
    private:
        vector<T> r;
};

template <class T>
void Combine<T>::combine(vector<T> a,int begin,int num)
{
    if(a.empty())
    {
        cout<<" 要组合的数组为空."<<endl;
        return;
    }
    if(num==0)
    {
        for_each(r.begin(),r.end(),[](T i)
        {
            cout<<i<<" ";
        });
        cout<<endl;
　　　　　return;
    }
    for(int i=begin;i<a.size();++i)
    {
        r.push_back(a.at(i));
        combine(a,i+1,num-1);
        r.pop_back();
    }
}

int main()
{
    vector<int> a;
    int n;
    cout<<" 请输入元素的个数:"<<endl;
    cin>>n;
    for(int i=0;i<n;++i)
    {
        int t;
        cin>>t;
        a.push_back(t);
    }
    
    int num;
    cout<<" 请输入要选择的个数:"<<endl;
    cin>>num;
    Combine<int> c;
    c.combine(a,0,num);
    return 0;
}

执行过程:

　　第一次for也就是开始:beign=0,i=0,num=2；进入下一次递归也就是第二次for循环，beign=1,i=1,num=1；第三次递归时num==0，输出，本次递归结束。返回到第二次递归也就是第二次for循环，i自增1

　　在第二次for循环里面进行递归也就是第四次for循环(有点绕。。。)，begin=1，i=2,num=1；第五次for循环时num==0，结束本次递归，退回到第二次for循环；i自增1，结果不符合for循环条件，第二次

　　for循环结束；以此推。。。（黑体加粗为同一层for循环）

排列组合

排列

组合

推荐阅读