std :: next_permutation实现说明 [英] std::next_permutation Implementation Explanation

问题描述

我很好奇如何实现 std：next_permutation ，所以我提取了 gnu libstdc ++ 4.7 版本和清理标识符和格式化以产生以下演示...

I was curious how std:next_permutation was implemented so I extracted the the gnu libstdc++ 4.7 version and sanitized the identifiers and formatting to produce the following demo...

#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 的含义是什么？他们在执行的不同部分有什么价值？

My questions are: How does it work? What is the meaning of i, j and k? What value do they hold at the different parts of execution? What is a sketch of a proof of its correctness?

显然，在进入主循环之前，它只是检查0或1个元素列表的情况。在主循环的入口处，我指向最后一个元素（不是一个过去的结束），并且列表至少为2个元素长。

Clearly before entering the main loop it just checks the trivial 0 or 1 element list cases. At entry of the main loop i is pointing to the last element (not one past end) and the list is at least 2 elements long.

推荐答案

让我们看看一些排列：

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

我们从一个排列到下一个排列？首先，让我们看看一些不同的东西。 我们可以将数字视为数字，并将排列视为数字。以这种方式查看问题我们要按升序顺序排列排列/数字。

How do we go from one permutation to the next? Firstly, let's look at things a little differently. We can view the elements as digits and the permutations as numbers. Viewing the problem in this way we want to order the permutations/numbers in "ascending" order.

当我们订购数字时，增加最小量。例如，当计数时，我们不计数1，2，3，10，...因为仍有4，5，...之间，虽然10大于3，有缺失的数字可以得到增加3较小的量。在上面的例子中，我们看到 1 长时间保持作为第一个数字，因为有很多重新排序的最后3数字，增加

When we order numbers we want to "increase them by the smallest amount". For example when counting we don't count 1, 2, 3, 10, ... because there are still 4, 5, ... in between and although 10 is larger than 3, there are missing numbers which can be gotten by increasing 3 by a smaller amount. In the example above we see that 1 stays as the first number for a long time as there are many reorderings of the last 3 "digits" which "increase" the permutation by a smaller amount.

那么我们什么时候最终使用 1 ？当最后3位数字没有更多的排列时。

当最后3位数字没有更多排列时？最后3位数字是以降序排列。

So when do we finally "use" the 1? When there are only no more permutations of the last 3 digits.
And when are there no more permutations of the last 3 digits? When the last 3 digits are in descending order.

Aha！这是理解算法的关键。 我们只在右侧的所有内容按降序排列时更改数字的位置 ，因为如果它不是按降序排列，那么还有更多排列要移动

Aha! This is key to understanding the algorithm. We only change the position of a "digit" when everything to the right is in descending order because if it isn't in descending order then there are still more permutations to go (ie we can "increase" the permutation by a smaller amount).

让我们回到代码：

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

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

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

在循环中， j 是一个元素， i 是它之前的元素。
然后，元素以升序排列，（ if（* i <* j））执行某些操作。

否则，如果整个事物按降序排列，（ if（i == begin））那么这是最后一个排列。

否则，我们继续，我们看到j和i减少。

From the first 2 lines in the loop, j is an element and i is the element before it.
Then, if the elements are in ascending order, (if (*i < *j)) do something.
Otherwise, if the whole thing is in descending order, (if (i == begin)) then this is the last permutation.
Otherwise, we continue and we see that j and i are essentially decremented.

现在我们了解了 if（i == begin）部分，所以我们需要了解的是 if（* i <* j） part。

We now understand the if (i == begin) part so all we need to understand is the if (*i < *j) part.

还要注意：如果元素是升序顺序...，它支持我们以前的观察，我们只需要对数字当一切都在右边是降序做一些事情。升序 if 语句本质上是找到最左边的位置，其中右侧的所有内容都是以降序。

Also note: "Then if the elements are in ascending order ..." which supports our previous observation that we only need to do something to a digit "when everything to the right is in descending order". The ascending order if statement is essentially finding the leftmost place where "everything to the right is in descending order".

让我们再看一些例子：

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

我们看到，当数字右侧的所有内容都按降序排列时，我们找到下一个最大的数字并将其放在前面，然后 put

We see that when everything to the right of a digit is in descending order, we find the next largest digit and put it in front and then put the remaining digits in ascending order.

让我们看看代码：

It k = end;

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

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

好吧，由于右边的内容是按降序排列，我们只需要从结束，我们看到在代码的前3行。

Well, since the things to the right are in descending order, to find the "next largest digit" we just have to iterate from the end, which we see in the first 3 lines of code.

接下来，我们交换次最大数字前面与 iter_swap（）语句，然后由于我们知道数字是第二大，我们知道右边的数字仍然是递减的顺序，所以按升序，我们只需要 reverse（） it。

Next, we swap the "next largest digit" to the front with the iter_swap() statement and then since we know that digit was the next largest, we know that the digits to the right are still in descending order, so to put it in ascending order, we just have to reverse() it.

这篇关于std :: next_permutation实现说明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！