std::next_permutation实现说明

Question

我很好奇std:next_permutation是如何实现的，所以我提取了gnu libstdc++ 4.7版本，并对标识符和格式进行了消毒，生成了以下演示...

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

template<typename It>
bool next_permutation(It begin, It end)
{
        if (begin == end)
                return false;

        It i = begin;
        ++i;
        if (i == end)
                return false;

        i = end;
        --i;

        while (true)
        {
                It j = i;
                --i;

                if (*i < *j)
                {
                        It k = end;

                        while (!(*i < *--k))
                                /* pass */;

                        iter_swap(i, k);
                        reverse(j, end);
                        return true;
                }

                if (i == begin)
                {
                        reverse(begin, end);
                        return false;
                }
        }
}

int main()
{
        vector<int> v = { 1, 2, 3, 4 };

        do
        {
                for (int i = 0; i < 4; i++)
                {
                        cout << v[i] << " ";
                }
                cout << endl;
        }
        while (::next_permutation(v.begin(), v.end()));
}

输出结果与预期一致：http://ideone.com/4nZdx

我的问题是:它是如何工作的？i、j和k的含义是什么？它们在执行的不同部分有什么价值？证明其正确性的草图是什么？

显然，在进入主循环之前，它只检查微不足道的0或1元素列表的情况。在主循环的入口处，i指向最后一个元素(不是一个过去的结尾)，列表至少有2个元素长。

主循环的主体中发生了什么？

Answer 1

gcc实现生成词典编排顺序的排列。Wikipedia对此的解释如下：

下面的算法在给定的排列之后按字典顺序生成下一个排列。它就地改变给定的排列。

1. 找到最大的索引k，使得ak < ak + 1。如果不存在这样的索引，则该排列是最后一个排列。
2. 找到最大的索引l，使得ak < al。由于k+1是这样的指标，l被很好地定义并且满足k
3. 与al互换ak。
4. 颠倒了从ak +1到最后一个元素a.

的顺序

Answer 2

Knuth在计算机编程艺术的7.2.1.2和7.2.1.3节中深入讨论了该算法及其推广。他称之为“算法L”--显然它可以追溯到13世纪。

Answer 3

下面是一个使用其他标准库算法的完整实现：

template <typename I, typename C>
    // requires BidirectionalIterator<I> && Compare<C>
bool my_next_permutation(I begin, I end, C comp) {
    auto rbegin = std::make_reverse_iterator(end);
    auto rend = std::make_reverse_iterator(begin);
    auto rsorted_end = std::is_sorted_until(rbegin, rend, comp);
    bool has_more_permutations = rsorted_end != rend;

    if (has_more_permutations) {
        auto rupper_bound = std::upper_bound(
            rbegin, rsorted_end, *rsorted_end, comp);
        std::iter_swap(rsorted_end, rupper_bound);
    }

    std::reverse(rbegin, rsorted_end);
    return has_more_permutations;
}

Demo