std::next_permutation Implementation Explanation

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

The output is as expected: http://ideone.com/4nZdx

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?

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.

What is going on in the body of the main loop?

34257 次浏览
小开

Gcc 的实现产生了字典序的排列。 维基百科解释如下:

下面的算法生成下一个排列 lexicographically after a given permutation. It changes the given 就位排列。

  1. 找到最大的索引 k，使得 a [ k ] < a [ k + 1]。如果没有这样的索引 exists, the permutation is the last permutation.
  2. 找出最大的索引 l，使得 a [ k ] < a [ l ] 定义良好，满足 k < l。
  3. 把 a [ k ]与 l [ l ]交换。
  4. Reverse the sequence from a[k + 1] up to and including the final element a[n].
小开
最佳答案

让我们来看一些排列:

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 我们希望将排列/数字按“升序”顺序排列.

当我们订购数字时，我们希望“以最小的数量增加它们”。例如，当我们计数时，我们不计数1,2,3,10，... ，因为中间还有4,5，... ，虽然10大于3，但有些数字可以通过将3增加一小部分得到。在上面的例子中，我们看到 1作为第一个数字保持了很长时间，因为后面的3个“数字”有许多重排序，这些重排序“增加”了排列的一个较小的数量。

那么，我们什么时候才能最终“使用”1? 当最后3位数字没有更多的排列时。
什么时候最后三位数字不再有排列了？当最后3位数字按降序排列时。

啊哈! 这是理解算法的关键。 我们只改变“数字”的位置时，所有向右的是降序 因为如果它不是按降序排列那么还有更多的排列(即我们可以“增加”一个较小的数量的排列)。

现在让我们回到代码:

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


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


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

从循环的前两行开始，j是一个元素，而 i是它前面的元素。< BR > 然后，如果元素按升序排列，(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
...

We see that when everything to the right of a digit is in descending order, we 找出下一个最大的数字放在前面 and then 把剩下的数字按升序排列.

让我们看看代码:

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.

接下来，我们用 iter_swap()语句将“下一个最大的数字”交换到前面，然后由于我们知道这个数字是下一个最大的，我们知道右边的数字仍然是降序排列的，所以要按升序排列，我们只需要 reverse()它。

小开

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

小开

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

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

演示

小开

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

小开 
#include <iostream>
#include <algorithm>
#include <iterator>


using namespace std;


int main() {


int int_array_11[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
do {
copy(begin(int_array_11), end(int_array_11), ostream_iterator<int>(cout, " "));
cout << endl;
} while (next_permutation(begin(int_array_11), end(int_array_11)));


return 0;
}

提交答案