Chinaunix首页 | 论坛 | 博客
  • 博客访问: 264949
  • 博文数量: 107
  • 博客积分: 305
  • 博客等级: 二等列兵
  • 技术积分: 417
  • 用 户 组: 普通用户
  • 注册时间: 2008-08-22 09:42
文章分类

全部博文(107)

文章存档

2014年(3)

2013年(41)

2012年(34)

2011年(28)

2008年(1)

分类: C/C++

2013-10-24 13:45:54


    STL提供了两个用来计算排列组合关系的算法,分别是next_permucation和prev_permucation。
1、next_permucation
    该函数会取得[first, last)所标示之序列的下一个排列组合。如果没有下一个排列组合,便返回false;否则返回true。
    这个算法有两个版本。版本一使用元素型别所提供的less-than操作符来决定下一个排列组合,版本二则是以仿函数comp来决定。
   
    算法简述如下所示。
    首先,从最尾端开始往前寻找两个相邻元素,令第一元素为*i,第二个元素为*ii,且满足*i < *ii。
    其次,找到这样一组相邻元素后,再从最尾端开始往前检验,找出第一个大于*i的元素,令为*j,将i,j对调,再将ii之后的所有元素颠倒排列。此即为所求之”下一个“排列组合。
    
    以下便是版本一的实现细节。
  1. template <class BidirectionlIterator>
  2. bool next_permutation(BidirectionlIterator first, BidirectionlIterator last)
  3. {
  4.     if(first == last)
  5.     {
  6.         return false;    //空区间
  7.     }

  8.     BidirectionlIterator i = first;
  9.     ++i;

  10.     if(i == last)
  11.     {
  12.         return false;    //只有一个元素
  13.     }

  14.     i = last;            //i 指向尾端
  15.     i--;

  16.     for( ; ; )
  17.     {
  18.         BidirectionlIterator ii = i;
  19.         --i;
  20.         //锁定一组(两个)相邻元素
  21.         if(*i < *ii)    //如果前一个元素小于后一个元素
  22.         {
  23.             BidirectionlIterator j = last;    //令j指向尾端
  24.             while(!(*i < *--j)                //从尾端往前找,直到遇上比*i大的元素
  25.             {
  26.                 ;
  27.             }
  28.             iter_swap(i, j);                //交换i,j
  29.             reverse(ii, last);                //将ii之后的元素全部逆向重排
  30.             return true;
  31.         }
  32.         if(i == first)
  33.         {
  34.             //进行至最后了
  35.             //全部逆向重排
  36.             reverse(first, last);
  37.             return false;
  38.         }
  39.         
  40.     }
  41. }

2、prev_permutation
    求前一个排列组合的做法简述如下所示。
    首先,从最尾端开始往前寻找两个相邻元素,零第一个元素为*i,第二个元素为*ii,且满足*i > *ii。
    其次,找到这样一组相邻元素后,再从最尾端开始往前检验,找出第一个小于*i的元素,令为*j,将i,j元素对调,再将ii之后的所有元素颠倒排列。
    此即为所求之”前一个“排列组合。
  1. template <class BidirectionlIterator>
  2. bool prev_permutation(BidirectionlIterator first, BidirectionlIterator last)
  3. {
  4.     if(first == last)
  5.     {
  6.         return false;    //空区间
  7.     }

  8.     BidirectionlIterator i = first;
  9.     ++i;

  10.     if(i == last)
  11.     {
  12.         return false;    //只有一个元素
  13.     }

  14.     i = last;            //i 指向尾端
  15.     i--;

  16.     for( ; ; )
  17.     {
  18.         BidirectionlIterator ii = i;
  19.         --i;
  20.         //锁定一组(两个)相邻元素
  21.         if(*i > *ii)    //如果前一个元素大于后一个元素
  22.         {
  23.             BidirectionlIterator j = last;    //令j指向尾端
  24.             while(!(*i > *--j)                //从尾端往前找,直到遇上比*i小的元素
  25.             {
  26.                 ;
  27.             }
  28.             iter_swap(i, j);                //交换i,j
  29.             reverse(ii, last);                //将ii之后的元素全部逆向重排
  30.             return true;
  31.         }
  32.         if(i == first)
  33.         {
  34.             //进行至最后了
  35.             //全部逆向重排
  36.             reverse(first, last);
  37.             return false;
  38.         }
  39.         
  40.     }
  41. }




阅读(1811) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~