c++ - 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什么？它们在执行的不同部分有什么价值？证明其正确性的草图是什么？jk

很明显，在进入主循环之前，它只检查琐碎的 0 或 1 元素列表案例。在主循环的入口处，我指向最后一个元素（不是一个过去的结尾），并且列表至少有 2 个元素长。

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

score 188 · Accepted Answer

让我们看一些排列：

我们如何从一个排列转到下一个排列？首先，让我们以不同的方式看待事物。我们可以将元素视为数字，将排列视为数字。以这种方式查看问题，我们希望以“升序”顺序排列排列/数字。

当我们订购数字时，我们希望“以最小的数量增加它们”。例如在计数时我们不计算 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 和 i 本质上是递减的。

我们现在了解了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()它。

score 45 · Accepted Answer

gcc 实现按字典顺序生成排列。维基百科解释如下：

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

找到满足 a[k] < a[k + 1] 的最大索引 k。如果不存在这样的索引，则排列是最后一个排列。

找到最大的索引 l 使得 a[k] < a[l]。由于 k + 1 是这样一个索引，所以 l 是很好定义的并且满足 k < l。

将 a[k] 与 a[l] 交换。

反转从 a[k + 1] 到最后一个元素 a[n] 的序列。

score 12 · Accepted Answer

Knuth 在The Art of Computer Programming 的7.2.1.2 和 7.2.1.3 节中深入介绍了该算法及其概括。他称之为“算法 L”——显然它可以追溯到 13 世纪。

score 9 · Accepted Answer

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

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;
}

演示

score 1 · Accepted Answer

使用.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。

c++ - std::next_permutation 实现说明

5 回答 5

Related

Reference