C++ STL next_permutation的达成原理

发布时间：2021-11-21 19:17:18 所属栏目：PHP教程来源：互联网

导读：next_permutation得到下一个排列，如对序列 a, b, c，每一个元素都比后面的小，它的下一个序列即为a, c, b next_permutation的函数原型如下： templateclass BidirectionalIterator bool next_permutation( BidirectionalIterator _First, BidirectionalIter

next_permutation得到下一个排列，如对序列 a, b, c，每一个元素都比后面的小，它的下一个序列即为a, c, b

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，后一个记为*t，并且满足*i < *t。然后再从尾端寻找另一个元素*j，如果满足*i < *j，即将第i个元素与第j个元素对调，并将第t个元素之后（包括t）的所有元素颠倒排序，即求出下一个序列了。

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 t = i;
        --i;
        if(*i < *t) {
            BidirectionalIterator j = last;
            while(!(*i < *--j));

            iter_swap(i, j);
            reverse(t, last);
            return true;
        }

        if(i == first) {
            reverse(first, last); //全逆向，即为最小字典序列，如cba变为abc
            return false;
        }
    }
}

所以如果到最后一个排列next_permutation会返回false，但是使用了这个方法后，序列会变成字典序列的第一个，如cba变成abc。就可以继续next了，可以参考next_permutation的用法，http://www.linuxidc.com/Linux/2013-04/82497.htm

在STL中，除了next_permutation外，还有一个函数prev_permutation，两者都是用来计算排列组合的函数。前者是求出下一个排列组合，而后者是求出上一个排列组合。

（编辑：云计算网_泰州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

php批量命名文件技巧	php读取文件内容几种正
php中读取大文件实现方	php打开远程文件的方法