的std :: next_permutation实施说明(std::next_permutation

我很好奇如何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:

让我们来看看一些排列：

我们如何从一个置换进入下一个？首先，让我们来看看不同的事情一点。 我们可以将元素作为数字和置换为数字 。通过这种方式，我们希望在“升序”以订购置换/数字看问题。

当我们订单号，我们要“以最小量增加他们。” 例如计数我们不计1，2，3时，10，...因为仍有4,5，...之间，虽然图10是大于3，有其可以由得到缺少数较小的量增加3。在上面的例子中，我们看到1停留作为用于作为有最后3“数字”，其通过一个较小的量“增加”置换许多重排序时间长的第一个数字。

所以，当我们终于“用” 1 ？当只有没有最后3个数字排列。
并且当最后3个位数不多的排列？当最后的3个数字按降序排列。

啊哈！这关键是理解的算法。 我们只有改变“数字”的位置时，一切右边是按降序排列 ，因为如果不按递减顺序则仍存在较多的排列去 （即我们可以通过一个较小的量“增加”排列）。

现在，让我们回到代码：

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

    if (*i < *j)
    { // ...
    }

    if (i == begin)
    { // ...
    }
}

从第一线2在回路中， j是一个元素， i是元素之前。
然后，如果元件是按升序排列，（ if (*i < *j) ）做一些事情。
否则，如果整个事情是按降序排列，（ if (i == begin) ），那么这是最后的排列。
否则，我们将继续和我们看到，J和我基本上递减。

我们现在明白了if (i == begin)一部分，所以我们需要了解的是if (*i < *j)一部分。

另外请注意：“那如果这些元素按升序排列......”，这支持了我们先前的观察，我们只需要做些什么来一个数字“当一切右边是按降序排列”。升序if语句基本上找到最左边的地方，“一切向权是降序”。

让我们再次在一些例子看看：

...
1 4 3 2
2 1 3 4
...
2 4 3 1
3 1 2 4
...

我们看到，当一切都以一个数字的右边是按降序排列，我们找到下一个大数字，把它放在面前 ，然后把剩下的数字按升序排列 。

让我们来看看代码：

It k = end;

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

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

好了，既然事情到右侧按降序排列，找到了“下一个最大的数字”我们只是从年底，我们将在第一3行代码见迭代。

接下来，我们交换了“下一个大数字”到前面与iter_swap()语句，然后因为我们知道数字是下一个最大的，我们知道，数字向右还是按降序排列，所以把它放在升序，我们只需要reverse()它。

Answer 2:

海湾合作委员会执行生成字典顺序排列。维基百科的解释，如下所示：

下面的算法给定的置换之后字典顺序生成下一个排列。它改变了就地给定的排列。
找到最大的索引k，使得[K] <一个[K + 1]。如果没有这样的索引存在，置换是最后的排列。
找到最大的索引升，使得[K] <一个[1]。由于k + 1是这样的索引，L是良好限定的并且满足ķ<升。
交换一个[K]与[1]。
从[K + 1]直到并包括最后一个元件[n]的反向序列。

Answer 3:

克努特进入这个算法及其在7.2.1.2节及计算机程序设计艺术 7.2.1.3的深入推广。他称之为“算法L” - 显然它的历史可以追溯到13世纪。

Answer 4:

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

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 next_unsorted = std::is_sorted_until(rbegin, rend, comp);
    bool at_final_permutation = (next_unsorted == rend);
    if (!at_final_permutation) {
        auto next_permutation = std::upper_bound(
            rbegin, next_unsorted, *next_unsorted, comp);
        std::iter_swap(next_unsorted, next_permutation);
    }
    std::reverse(rbegin, next_unsorted);
    return !at_final_permutation;
}

演示

Answer 5:

有上的自我解释可能implemetation cppreference使用<algorithm> 。

template <class Iterator>
bool next_permutation(Iterator first, Iterator last) {
    if (first == last) return false;
    Iterator i = last;
    if (first == --i) return false;
    while (1) {
        Iterator i1 = i, i2;
        if (*--i < *i1) {
            i2 = last;
            while (!(*i < *--i2));
            std::iter_swap(i, i2);
            std::reverse(i1, last);
            return true;
        }
        if (i == first) {
            std::reverse(first, last);
            return false;
        }
    }
}

切换到下一个字典顺序排列（就地）和否则排序存在返回true，如果它不存在返回false的内容。

文章来源: std::next_permutation Implementation Explanation