stl 中 next_permutation、prev_permutation的原理和使用

next_permutation实现原理
在《STL源码解析》中找到了这个函数,在此也简单叙述一下原理:
在STL中,除了next_permutation外,还有一个函数prev_permutation,两者都是用来计算排列组合的函数。前者是求出下一个排列组合,而后者是求出上一个排列组合。所谓“下一个”和“上一个”,书中举了一个简单的例子:对序列 {a, b, c},每一个元素都比后面的小,按照字典序列,固定a之后,a比bc都小,c比b大,它的下一个序列即为{a, c, b},而{a, c, b}的上一个序列即为{a, b, c},同理可以推出所有的六个序列为:{a, b, c}、{a, c, b}、{b, a, c}、{b, c, a}、{c, a, b}、{c, b, a},其中{a, b, c}没有上一个元素,{c, b, a}没有下一个元素。
next_permutation的函数原型如下:

template<class BidirectionalIterator>
bool next_permutation(
      BidirectionalIterator _First,
      BidirectionalIterator _Last
);
template<class BidirectionalIterator, class BinaryPredicate>
bool next_permutation(
      BidirectionalIterator _First,
      BidirectionalIterator _Last,
      BinaryPredicate _Comp
 );

对于第二个重载函数的第三个参数,默认比较顺序为小于。如果找到下一个序列,则返回真,否则返回假。
函数实现原理如下:
在当前序列中,从尾端往前寻找两个相邻元素,前一个记为*i,后一个记为*ii,并且满足*i < *ii。然后再从尾端寻找另一个元素*j,如果满足*i < *j,即将第i个元素与第j个元素对调,并将第ii个元素之后(包括ii)的所有元素颠倒排序,即求出下一个序列了。
代码实现如下:

template<class BidirectionalIterator>
bool next_permutation(
      BidirectionalIterator first,
      BidirectionalIterator last
)
{
    if(first == last)
        return false; //空序列
    BidirectionalIterator i = first;
    ++i;
    if(i == last)
        return false;  //一个元素,没有下一个序列了
    i = last;
    --i;
    for(;;) {
        BidirectionalIterator ii = i;
        --i;
        if(*i < *ii) {
            BidirectionalIterator j = lase;
            while(!(*i < *--j));
            iter_swap(i, j);
            reverse(ii, last);
            return true;
        }
        if(i == first) {
            reverse(first, last);  //全逆向,即为最小字典序列,如cba变为abc
            return false;
        }
    }
}

prev_permutation实现类似,就是反向查找。
例子:

#include<iostream>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	    string str = "abcd";
	    do{
		        cout<<str<<endl;
    	}while(next_permutation(str.begin(), str.end()));
	    cout<<"after loop:\n"<<str<<endl;
    	return 0;
}

输出:

[zhangjun@s3 leetcode]$ ./strtest
abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba
after loop:
abcd

 
最后一个排列没有下一个排列,用next_permutation会返回false,但使用这个方法后,序列会变成字典序列的第一个。如dcba变成abcd。

Leave a Reply

Your email address will not be published. Required fields are marked *