C++ std::next_permutation 实现说明
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/11483060/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
std::next_permutation Implementation Explanation
提问by Andrew Tomazos
I was curious how std:next_permutationwas implemented so I extracted the the gnu libstdc++ 4.7version and sanitized the identifiers and formatting to produce the following demo...
我很好奇是如何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()));
}
The output is as expected: http://ideone.com/4nZdx
输出如预期：http: //ideone.com/4nZdx
My questions are: How does it work? What is the meaning of i, jand k? What value do they hold at the different parts of execution? What is a sketch of a proof of its correctness?
我的问题是：它是如何工作的？是什么意思i，j和k？它们在执行的不同部分具有什么价值？什么是证明其正确性的草图？
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.
很明显，在进入主循环之前，它只检查微不足道的 0 或 1 元素列表情况。在主循环的入口处，我指向最后一个元素（不是最后一个），并且列表至少有 2 个元素长。
What is going on in the body of the main loop?
主循环体中发生了什么？
回答by flight
Let's look at some permutations:
让我们看看一些排列：
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.
我们如何从一个排列到下一个排列？首先，让我们换个角度看问题。我们可以将元素视为数字，将排列视为数字。以这种方式查看问题，我们希望按“升序”顺序排列排列/数字。
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 1stays 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, 2, 3, 10, ... 因为中间还有 4, 5, ... 虽然 10 大于 3，但仍有缺失的数字可以通过以较小的量增加 3。在上面的示例中，我们看到它1长时间保持为第一个数字，因为最后 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.
那么我们什么时候最终“使用” 1？当只有最后 3 位数字没有更多排列时。
什么时候不再有最后 3 位数字的排列？当最后 3 位数字按降序排列时。
Aha! This is key to understanding the algorithm. We only change the position of a "digit" when everything to the right is in descending orderbecause 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).
啊哈！这是理解算法的关键。我们只在右侧的所有内容都按降序排列时更改“数字”的位置，因为如果它不是按降序排列，那么还有更多的排列要进行（即我们可以将排列“增加”一个较小的数量） .
Let's now go back to the code:
现在让我们回到代码：
while (true)
{
It j = i;
--i;
if (*i < *j)
{ // ...
}
if (i == begin)
{ // ...
}
}
From the first 2 lines in the loop, jis an element and iis 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.
从循环中的前 2 行开始，j是一个元素并且i是它之前的元素。
然后，如果元素按升序排列，则 ( if (*i < *j)) 执行某些操作。
否则，如果整个事物按降序排列， ( if (i == begin)) 那么这是最后一个排列。
否则，我们继续，我们看到 j 和 i 基本上是递减的。
We now understand the if (i == begin)part so all we need to understand is the if (*i < *j)part.
我们现在了解了if (i == begin)零件，所以我们需要了解的只是if (*i < *j)零件。
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 ifstatement is essentially finding the leftmost place where "everything to the right is in descending order".
还要注意：“那么如果元素是按升序排列的……”这支持我们之前的观察，即我们只需要对一个数字“当右边的所有东西都按降序排列时”做一些事情。升序if语句本质上是找到“右边的所有东西都按降序排列”的最左边的地方。
Let's look again at some examples:
让我们再看一些例子：
...
1 4 3 2
2 1 3 4
...
2 4 3 1
3 1 2 4
...
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 frontand then put the remaining digits in ascending order.
我们看到，当一个数字右边的所有数字都按降序排列时，我们找到下一个最大的数字并将其放在前面，然后将剩余的数字按升序排列。
Let's look at the code:
让我们看一下代码：
It k = end;
while (!(*i < *--k))
/* pass */;
iter_swap(i, k);
reverse(j, end);
return true;
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.
好吧，因为右边的东西是按降序排列的，为了找到“下一个最大的数字”，我们只需要从末尾开始迭代，我们在前 3 行代码中看到了这一点。
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.
接下来，我们将“下一个最大的数字”与iter_swap()语句交换到前面，然后因为我们知道那个数字是下一个最大的数字，我们知道右边的数字仍然是降序的，所以把它放在升序中，我们只需要reverse()它。
回答by TemplateRex
The gcc implementation generates permutations in lexicographical order. Wikipediaexplains it as follows:
gcc 实现按字典顺序生成排列。维基百科解释如下：
The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.
- Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
- Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
- Swap a[k] with a[l].
- Reverse the sequence from a[k + 1] up to and including the final element a[n].
以下算法在给定排列后按字典顺序生成下一个排列。它就地更改给定的排列。
- 找到最大的索引 k，使得 a[k] < a[k + 1]。如果不存在这样的索引，则排列是最后排列。
- 找到最大的索引 l，使得 a[k] < a[l]。由于 k + 1 是这样的索引，所以 l 是明确定义的并且满足 k < l。
- 将 a[k] 与 a[l] 交换。
- 反转从 a[k + 1] 到并包括最终元素 a[n] 的序列。
回答by TemplateRex
Knuth goes into depth about this algorithm and its generalizations in sections 7.2.1.2 and 7.2.1.3 of The Art of Computer Programming. He calls it "Algorithm L" -- apparently it dates back to the 13th century.
Knuth 在The Art of Computer Programming 的第 7.2.1.2 和 7.2.1.3 节中深入介绍了该算法及其概括。他称之为“算法 L”——显然它可以追溯到 13 世纪。
回答by Brian Rodriguez
Here's a complete implementation using other standard library algorithms:
这是使用其他标准库算法的完整实现：
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 next_permutation_rend = std::upper_bound(
rbegin, rsorted_end, *rsorted_end, comp);
std::iter_swap(rsorted_end, next_permutation_rend);
}
std::reverse(rbegin, rsorted_end);
return has_more_permutations;
}
回答by Shreevardhan
There is a self explanatory possible implemetation on cppreferenceusing <algorithm>.
使用.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;
}
}
}
Change the content to lexicographically next permutation (in-place) and return true if exists otherwise sort and return false if it doesn't exist.
将内容更改为按字典顺序排列的下一个排列（就地），如果存在则返回 true 否则排序并返回 false 如果它不存在。
