STL学习之排列组合算法算法

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

template <class BidirectionlIterator>
bool next_permutation(BidirectionlIterator first, BidirectionlIterator last)
{
    if(first == last)
    {
        return false;    //空区间
    }

    BidirectionlIterator  i = first;
    ++i;

    if(i == last)
    {
        return false;    //只有一个元素
    }

    i = last;            //i 指向尾端
    i--;

    for( ; ; )
    {
        BidirectionlIterator ii = i;
        --i;
        //锁定一组（两个）相邻元素
        if(*i < *ii)    //如果前一个元素小于后一个元素
        {
            BidirectionlIterator j = last;    //令j指向尾端
            while(!(*i < *--j)                //从尾端往前找，直到遇上比*i大的元素
            {
                ;
            }
            iter_swap(i, j);                //交换i，j
            reverse(ii, last);                //将ii之后的元素全部逆向重排
            return true;
        }
        if(i == first)
        {
            //进行至最后了
            //全部逆向重排
            reverse(first, last);
            return false;
        }

    }
}

2、prev_permutation
    求前一个排列组合的做法简述如下所示。
    首先，从最尾端开始往前寻找两个相邻元素，零第一个元素为*i，第二个元素为*ii，且满足*i > *ii。
    其次，找到这样一组相邻元素后，再从最尾端开始往前检验，找出第一个小于*i的元素，令为*j，将i，j元素对调，再将ii之后的所有元素颠倒排列。
    此即为所求之”前一个“排列组合。

template <class BidirectionlIterator>
bool prev_permutation(BidirectionlIterator first, BidirectionlIterator last)
{
    if(first == last)
    {
        return false;    //空区间
    }

    BidirectionlIterator  i = first;
    ++i;

    if(i == last)
    {
        return false;    //只有一个元素
    }

    i = last;            //i 指向尾端
    i--;

    for( ; ; )
    {
        BidirectionlIterator ii = i;
        --i;
        //锁定一组（两个）相邻元素
        if(*i > *ii)    //如果前一个元素大于后一个元素
        {
            BidirectionlIterator j = last;    //令j指向尾端
            while(!(*i > *--j)                //从尾端往前找，直到遇上比*i小的元素
            {
                ;
            }
            iter_swap(i, j);                //交换i，j
            reverse(ii, last);                //将ii之后的元素全部逆向重排
            return true;
        }
        if(i == first)
        {
            //进行至最后了
            //全部逆向重排
            reverse(first, last);
            return false;
        }

    }
}