我很好奇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个元素长。
主循环的主体发生了什么？
让我们看看一些排列：
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
...
我们如何从一个排列进入下一个排列？首先，让我们从不同的角度来看待事情我们可以将元素视为数字，将排列视为数字。以这种方式查看问题我们希望按"升序"排列排列/数字。
当我们订购数字时，我们希望"以最小的数量增加"。例如，当计数时，我们不计算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)
{ // ...
}
}
从循环的前两行开始，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()即可。
gcc实现按字典顺序生成排列。维基百科解释如下：
以下算法生成下一个排列在给定的排列之后按字典顺序排列。它改变了给定排列到位。
- 找到最大的索引k，使得a[k]<a[k+1]。如果没有这样的索引存在，该排列是最后一个排列
- 找到最大的索引l，使得a[k]<a[l]。由于k+1是这样一个索引，所以l是定义良好并且满足k<l
- 用[l]替换[k]
- 反转从a[k+1]到最后一个元素a[n]的顺序
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>可以在cpprreference上实现一个不言自明的可能实现。
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;
}