//全排列算法：    
//        
//    思路很簡單很經典，目的是由小到大依次輸出結果；非遞歸方法    
//    不知道該怎樣描述，所以給個例子：    
//例子:    
//     假如當前排列dbeca，求其下個排列(經過人工排列，結果顯然是dcabe)。    
//     1)從右向左尋找第一個由小到大的（長度為2的）字符串，這里是be    
//     2)那么b后面是字符串eca，其中比b大的最小字符是c    
//     3)將b和c交換，則現在的排列是dceba    
//     4)將c后面的字符串eba由小到大排序，則現在的排列是dcabe（這就是結果）    
//     5)重復第1步    
//使用語言：c++    
//經測試：10個字符全排列需要8分鐘左右，主要費時在打印結果在屏幕；如果不打印，    
//        僅需10秒左右；cpu是AMD 3500+    
//如有錯誤，請指正！    
  
#include "stdafx.h"    
#include <iostream>    
#include <vector>    
#include <cassert>    
#include <algorithm>    
  
  
typedef char Kind;//定義比較數據的種類，這里是char。只是為了修改方便    
  
bool Compare(const std::vector<Kind>& Array, int nIndex1, int nIndex2)   
{   
//比較Array[nIndex1]和Array[nIndex2]的大小;如果大于，則返回true；否則返回false；    
//[IN]Array: 一個排列    
//[IN]nIndex1, nIndex2: Array的下標    
//附：定義這個函數只是為了增強易修改行；如果Kind是其他類型，比如是string類型，    
//    只修改這函數的比較規則就行了    
//注意：顯然忽略了相等的情況，假設了各個元素不相等    
  
 assert(Array[nIndex1] != Array[nIndex2]);   
  
 return ( Array[nIndex1] > Array[nIndex2] );   
}   
  
int FirstSmallToBig(const std::vector<Kind>& Array)   
{   
//在Array中，從右向左尋找第一個由小到大的（長度為2的）字符串，并返回此字符串在    
//    Array中的位置    
//[IN]Array: 一個排列    
//返回值：尋找到的字符串在Arrray中的位置；如果返回值為-1表示沒有找到    
  
 int nPos = -1;//返回值    
  
 for(int i=Array.size()-1; i>=1; --i)   
 {   
  if( Compare(Array, i, i-1) )   
  {   
   nPos = i-1;   
   break;   
  }   
 }   
  
 return nPos;   
}   
  
int MinBigThan(const std::vector<Kind>& Array, int nIndex)   
{   
//獲得Array[nIndex+1]到Array末尾中，比Array[nIndex]大的最小元素在Array中的位置    
//[IN]Array: 一個排列    
//[IN]nIndex: Array的下標    
//返回值：Array[nIndex+1]到Array末尾中，比Array[nIndex]大的最小元素在Array中的    
//        位置(即下標)    
  
 int nPos = -1;//返回值    
 std::vector<Kind> v;//用于存儲（Array[nIndex+1]到Array末尾中）比Array[nIndex]大的最小元素    
 v.push_back( Array[nIndex] );   
 std::vector<Kind>::iterator it = v.begin();   
  
 //尋找第一個比Array[nIndex]大的元素    
 for(int i=nIndex+1; i<Array.size(); ++i)   
 {   
  if( Compare(Array, i, nIndex) )   
  {   
   v[0] = Array[i];   
   nPos = i;   
   break;   
  }   
 }   
 ++i;   
 if( i == Array.size() )    
 {    
  assert(nPos != -1);   
     return nPos;   
 }   
  
 assert(v[0] != Array[nIndex]);   
  
 //獲得Array[nIndex+1]到Array末尾中，比Array[nIndex]大的最小元素在Array中的位置    
 for(; i<=Array.size(); ++i)   
 {   
  if( Compare(Array, i, nIndex) && Array[i]<v[0])   
  {   
   v[0] = Array[i];   
   nPos = i;   
  }   
 }   
  
 assert(nPos != -1);   
 return nPos;   
}   
  
  
void Swap(std::vector<Kind>& Array, int nIndex1, int nIndex2)   
{   
//Array[nIndex1]和Array[nIndex2]交換元素    
  
 assert( nIndex1>=0 && nIndex1<Array.size() );   
 assert( nIndex2>=0 && nIndex2<Array.size() );   
  
 std::vector<Kind> temp;   
 temp.push_back(Array[nIndex1]);   
 Array[nIndex1] = Array[nIndex2];   
 Array[nIndex2] = temp[0];   
  
}   
  
void Print(const std::vector<Kind>& Array)   
{   
//打印結果    
  
 using std::cout;   
 using std::endl;   
  
 for(int i=0; i<Array.size(); ++i)   
  cout<<Array[i];   
 cout<<endl;   
  
}   
void Permutation(std::vector<Kind>& Array)   
{   
//求全排列    
//[IN]Array: 全排列的數組；要求升序排列    
  
 int nIndex1,nIndex2;   
  
 int nNum=0;//用于統計結果的個數    
  
 Print(Array);//打印一個結果    
 nNum++;   
 while(1)   
 {    
  nIndex1 = FirstSmallToBig( Array );//從右向左尋找第一個由小到大的（長度為2的）字符串    
  if(nIndex1 == -1) break;//如果找不到，表示已經是降序排列，程序結束。    
  nIndex2 =  MinBigThan( Array, nIndex1 );//獲得Array[nIndex+1]到Array末尾中，比Array[nIndex]大的最小元素在Array中的位置    
  Swap( Array,  nIndex1,  nIndex2 );//Array[nIndex1]和Array[nIndex2]交換元素    
  std::sort( Array.begin()+nIndex1+1 , Array.end() );//對Array[nIndex+1]到Array末尾的元素排序    
  
  Print(Array);//打印一個結果    
  nNum++;   
 }   
  
 std::cout<<"結果的個數："<<nNum<<std::endl;   
  
}   
  
const int nsize =10;//元素的個數    
int main(int argc, char* argv[])   
{   
 Kind a[20] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n'};    
 std::vector<Kind> Array(a,a+nsize);   
  
 Permutation(Array);   
  
 return 0;   
}   

STL算法之 next_permutation、prev_permutation 的原理和實現