Error

C++博客 首页 新随笔 联系 聚合 管理
  217 Posts :: 61 Stories :: 32 Comments :: 0 Trackbacks

 

 
//全排列算法:    
//        
//    思路很简单很经典,目的是由小到大依次输出结果;非递归方法    
//    不知道该怎样描述,所以给个例子:    
//例子:    
//     假如当前排列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 == -1break;//如果找不到,表示已经是降序排列,程序结束。    
  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 的原理和实现

两个函数类似,重点介绍next_permutation.

template <class BidirectionalIterator>

  bool next_permutation (BidirectionalIterator first,

                         BidirectionalIterator last );

 

template <class BidirectionalIterator, class Compare>

  bool next_permutation (BidirectionalIterator first,

                         BidirectionalIterator last, Compare comp);

 

简介:得到下一个排列组合

默认是按字典序,比如abc->acb->bac->bca->cab->cba

 

算法描述:

1、从尾部开始往前寻找两个相邻的元素

第1个元素i,第2个元素j(从前往后数的),且i<j

2、再从尾往前找第一个大于i的元素k。将i、k对调

3、[j,last)范围的元素置逆(颠倒排列)

 

运行过程:

next: 01234

-> i=3,j=4

-> k=4,对调后01243

-> j指向最后一个元素,故结果为01243

 

next: 01243

-> i=2,j=4

-> k=3,对调后01342

-> j指向4,颠倒后为01324 即结果

 

...

next: 01432

-> i=1,j=4

-> k=2,对调后02431

-> j指向4,颠倒02134

 

按默认字典序的内部实现(带仿函数的类似):

#include <algorithm>

#include <iostream>

 

template<typename BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last)
{
    // 空区间
    if(first == last)
        return false;
    BidirectionalIterator i = first;
    ++i;
    // 只有一个元素
    if(i == last)
        return false;

    // i指向尾部
    i = last;
    --i;
    for (;;)
    {
        // i是j的上一个元素
        BidirectionalIterator j = i;
        --i;
        if(*i < *j)
        {
            // 由尾部往前找到第一个比*i大的元素,并交换i,k
            BidirectionalIterator k = last;
            while(!(*i < *--k))
                ;
            std::iter_swap(i, k);
            // 将[j,last)的元素逆向重排
            std::reverse(j, last);
            return true;
        }
        // 到最前面了
        if(i == first)
        {
            std::reverse(first, last);
            return false;
        }
    }
}

int main()
{
    int arr[] = {1, 2, 3};
    do 
    {
        std::cout<<arr[0]<<" "<<arr[1]<<" "<<arr[2]<<std::endl;
    } while (next_permutation(arr, arr + 3));
    prev_permutation()
    // 到最前面的时候数组被reverse了
    std::cout<<"last status: ";
    std::cout<<arr[0]<<" "<<arr[1]<<" "<<arr[2]<<std::endl;
    return 0;
}

 

prev_permutation与next_permutation不同之处就是

算法第一步:从尾部开始往前寻找两个相邻的元素

第1个元素i,第2个元素j(从前往后数的),且i>j(next_permutation条件是i<j)

posted on 2012-11-21 11:17 Enic 阅读(103) 评论(0)  编辑 收藏 引用 所属分类: stl陷阱与技巧

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理