Error

 

//全排列算法：    
//        
//    思路很简单很经典，目的是由小到大依次输出结果；非递归方法    
//    不知道该怎样描述，所以给个例子：    
//例子:    
//     假如当前排列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 的原理和实现