排列

全排列是将一组数按一定顺序进行排列，如果这组数有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 
      
       #include 
       
        #include 
        
         using namespace std;template 
         
          class Perm{    public:        //由于vector本身就是模板,在其模板参数未确定之前,也就是具体类型没有确定之前,这个T是未知的        //typename就是告诉编译器先不管具体类型，等模板实例化的时候再确定         void perm(vector
          
            &a,typename vector
           
            ::iterator begin); bool is_swap(typename vector
            
             ::iterator i,typename vector
             
              ::iterator j); private: static int i;};template 
              
               int Perm
               
                ::i=0;template 
                
                 bool Perm
                 
                  ::is_swap(typename vector
                  
                   ::iterator i,typename vector
                   
                    ::iterator j){ for(typename vector
                    
                     ::iterator k=i;k!=j;++k) if(*k==*j) return false; return true; }template 
                     
                      void Perm
                      
                       ::perm(vector
                       
                         &a,typename vector
                        
                         ::iterator begin){ if(begin==a.end()) { cout<<" 第"<<++i<<" 个排列为:"; for_each(a.begin(),a.end(),[](int i) { cout<
                         <<" "; }); cout<
                          

a; int n; cout<<" 请输入元素的个数:"<

>n; for(int i=0;i

>t; a.push_back(t); } Perm

p; p.perm(a,a.begin()); return 0;}

 组合

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

#include 
      
       #include 
       
        #include 
        
         using namespace std;template 
         
           class Combine{    public:        void combine(vector
          
            a,int begin,int num);    private:        vector
           
             r;};template 
            
             void Combine
             
              ::combine(vector
              
                a,int begin,int num){ if(a.empty()) { cout<<" 要组合的数组为空."<
               

a; int n; cout<<" 请输入元素的个数:"<

>n; for(int i=0;i

>t; a.push_back(t); } int num; cout<<" 请输入要选择的个数:"<

>num; Combine

c; c.combine(a,0,num); return 0;}