从零开始的 STL 实现记录：Algorithm-4.3

前言

本节将会分析 stl_algo.h 中 next_permutation 与 prev_premutation 的实现，之所以分析这两个函数倒不是因为他们的实现有多么精彩（像 copy() 那样），而是“下一个排列”与“上一个排列”这种问题十分经典，解法也很固定。

STL 提供了两个用来计算排列组合关系的算法，分别是 next_permucation 和 prev_permutation。首先我们必须了解什么是“下一个”排列组合,什么是“前一个”排列组合。考虑三个字符所组成的序列 {a,b,c}。这个序列有六个可能的排列组合: abc，acb，bac，bca，cab，cba。这些排列组合根据 less-than 操作符做字典顺序的排序。也就是说，abc 名列第一，因为每一个元素都小于其后的元素。acb是次一个排列组合，因为它是固定了a（序列内最小元素）之后所做的新组合。同样道理、那些固定b （序列内次小元素）而做的排列组合，在次序上将先于那些固定 c 而做的排列组合。以 bac 和 bca 为例，bac 在 bca之前，因为序列 ac 小于序列 ca。面对bca，我们可以说其前一个排列组合是 bac，而其后一个排列组合是 cab。序列 abc 没有“前一个”排列组合，cba 没有“后一个”排列组合。

next_permutation

next_pernutation() 会取得 [first ,last) 所标示之序列的下一个排列组合。如果没有下一个排列组合，便返回 false；否则返回 true。

该算法同样也提供了一个以仿函数 comp 来决定排列的大小关系的重载。

该函数的流程如下：

• 首先，从最尾端开始往前寻找两个相邻元素，令第一元素为 *i，第二元素为 *ii，且满足 *i < *ii。
• 找到这样一组相邻元素后，再从最尾端开始往前检验,找出第一个大于 *i 的元素，令为 *j。
• 将 i,j 元素对调，再将 ii 之后的所有元素颠倒排列，此即所求之“下一个”排列组合。

以下是以 [0,1,2,3,4] 为例，逐次执行 next_permutation 的过程。

知道了逻辑，下面的代码就很好理解了。

/*****************************************************************************************/
// next_permutation
// 取得[first, last)所标示序列的下一个排列组合，如果没有下一个排序组合，返回 false，否则返回 true
/*****************************************************************************************/

/// @brief 取得[first, last)所标示序列的下一个排列组合，如果没有下一个排序组合，返回 false，否则返回 true
template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last) {
    auto i = last;
    if (first == last || first == --i) return false;
    for (;;) {
        // 从尾部向前查找
        auto ii = i;
        // 找到相邻元素满足 *i < *ii
        if (*--i < *ii) {
            // 从尾部向前查找第一个大于 *i 的元素 *j
            auto j = last;
            while (!(*i < *--j)) {}
            // 交换 *i 和 *j
            tinystl::iter_swap(i, j);
            // 将 ii 之后的元素颠倒排列
            tinystl::reverse(ii, last);
            return true;
        }
        if (i == first) {
            // 进行到这里时，当前序列已经是“最后一个”排列组合，
            // 将整个序列逆向排列，使其成为“第一个”排列组合
            tinystl::reverse(first, last);
            return false;
        }
    }
}

/// @brief 重载版本使用函数对象 comp 代替比较操作
template <class BidirectionalIterator, class Compare>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp) {
    auto i = last;
    if (first == last || first == --i) return false;
    for (;;) {
        auto ii = i;
        if (comp(*--i, *ii)) {
            auto j = last;
            while (!comp(*i, *--j)) {}
            tinystl::iter_swap(i, j);
            tinystl::reverse(ii, last);
            return true;
        }
        if (i == first) {
            tinystl::reverse(first, last);
            return false;
        }
    }
}

比较奇怪的是，当目前的排列组合已经是最后一个排列组合时，这个算法会将整个区间逆转，即回到第一个排列组合，这种做法比较奇怪，可能是出于方便考虑吧。

vector<char> v1 = {'c', 'b', 'a'};
next_permutation(v1.begin(), v1.end());
for (auto c : v1)
    cout << c << " ";  // a b c 

由于没有下一个排列组合时，会返回 false，因此可以将返回值作为判断条件。

vector<char> chars = {'a', 'b', 'c'};
do {
    cout << chars[0] << chars[1] << chars[2] << endl;
} while (next_permutation(chars.begin(), chars.end()));

return 0;

// abc
// acb
// bac
// bca
// cab
// cba

prev_permutation

prev_permutation 顾名思义，就是取得前一个组合，逻辑刚好与 next_permutation 相反，实现上也几乎相同。唯二不同的两个条件判断已经在下面的函数流程中标出。

该函数的流程如下：

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

/*****************************************************************************************/
// prev_permutation
// 取得[first, last)所标示序列的上一个排列组合，如果没有上一个排序组合，返回 false，否则返回 true
/*****************************************************************************************/

/// @brief 取得[first, last)所标示序列的上一个排列组合，如果没有上一个排序组合，返回 false，否则返回 true
template <class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last) {
    auto i = last;
    if (first == last || first == --i) return false;
    for (;;) {
        // 从尾部向前查找
        auto ii = i;
        // 找到第一对相邻元素，满足 *i > *ii
        if (*ii < *--i) {
            // 从尾部向前查找第一个小于 *i 的元素 *j
            auto j = last;
            while (!(*--j < *i)) {}
            // 交换 *i 和 *j
            tinystl::iter_swap(i, j);
            // 将 ii 之后的元素颠倒排列    
            tinystl::reverse(ii, last);  
            return true;
        }
        if (i == first) {
            // 进行到这里时，当前序列已经是“第一个”排列组合，
            // 将整个序列逆向排列，使其成为“最后一个”排列组合
            tinystl::reverse(first, last);
            return false;
        }
    }
}

/// @brief 重载版本使用函数对象 comp 代替比较操作
template <class BidirectionalIterator, class Compare>
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp) {
    auto i = last;
    if (first == last || first == --i) return false;
    for (;;) {
        auto ii = i;
        if (comp(*ii, *--i)) {
            auto j = last;
            while (!comp(*--j, *i)) {}
            tinystl::iter_swap(i, j);
            tinystl::reverse(ii, last);
            return true;
        }
        if (i == first) {
            tinystl::reverse(first, last);
            return false;
        }
    }
}

当目前的排列组合已经是第一个排列组合时，该算法也会将整个区间逆转，以回到最后一个排列组合。

总结

本节简要介绍了 next_permutation 与 prev_premutation 的实现，这两个函数的实现朴实无华，没有什么技巧，因此也就不进行测试什么的了，但算法流程需要理解，当心面试做到。