输出全排列

题目：给一串字符，求他的全排列

     如：{1,2,3}的全排列：   1 2 3

                                    1 3 2

                                    2 1 3

                                    2 3 1

                                    3 1 2

                                    3 2 1

解法：

1.首先按志典顺序进行排序（得到 1 2 3）

2.根据标记从后往前比较相邻两数据，若前者小于后者（2<3），标志前者为X1(2),位置PX(1),再次重后往前搜索第一个不小于X1(2)的数据，标记为X2(3)。交换X1(2)，X2(3)，然后把[PX+1，last)标记范围逆转。得到一个新的排列完成。

3.按方法2，循环往复，知道，找不到前者小于后则的时候，表明已经没有新的排列。

正确性分析：（为什么这样就可以保证得到的为最小递增）

当前排列和下一次排列：从第一个元素开始当前数列与下一次数列不同的数据位置是PX，并且下一次数列在PX位置的数据为X2。由步骤2可以得出：在下一次得到的数列中[PX+1，last)总是递减的，[first,PX)没有改变，因为X2>X1,所以不管当前的[PX+1,last]怎样排列都比下一次数列大，反转[PX+1，last）使此子数列(递增)为最小。从而保证的下一次数列为当前数列的字典序排列的next。

如： 当前数列为 1 2 4 3

       由步骤2得：X1=2，X2=3， PX=1（从0开始计数）

       交换X1，X2得数列1 3 4 2, [PX+1,last)=[4,2]是递减的

       [4,3] > [4,2]

       翻转 [4,2]得到[2,4]，所以下一次数列为 1 3 2 4

算法：在C++STL中已经实现了该算法，名为：next_permutation()

  1: #include<iostream>


  2: #include<vector>


  3: #include<algorithm>


  4: using namespace std ;


  5: 


  6: bool permutation(vector<int>& a)


  7: {


  8:     int firstMin ;


  9:     int firstMax ;


 10:     int i ;


 11:     int pos ;


 12:     for(i=a.size()-1;i>0;--i)


 13:     {


 14:         if (a[i-1]<a[i]){


 15:             firstMin = a[i-1] ;


 16:             break ;


 17:         }


 18:     }


 19:     if (i==0){


 20:         reverse(a.begin()+pos,a.end());


 21:         return false ;


 22:     }


 23:     pos = i ;


 24:     for (i=a.size()-1;i>=0;--i){


 25:         if(a[i]>firstMin){


 26:             firstMax = a[i] ;


 27:             break ;


 28:         }


 29:     }


 30:     if (-1==i){


 31:         return false ;


 32:     }


 33:     swap(a[pos-1],a[i]) ;


 34:     reverse(a.begin()+pos,a.end());


 35:     return true ;


 36: 


 37: }


 38: void print(int i){


 39:     cout << i << " " ;


 40: }


 41: int main()


 42: { 


 43:     vector<int> vInt ; 


 44:     vInt.push_back(5) ;


 45:     vInt.push_back(2);


 46:     vInt.push_back(1) ;


 47:     vInt.push_back(4) ;


 48:     sort(vInt.begin(),vInt.end()) ;


 49:     do{


 50:         for_each(vInt.begin(),vInt.end(),print) ;


 51:         cout << endl ;


 52:     }while(permutation(vInt)); 


 53: }