std :: next_permutation实现说明
我很好奇如何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是什么意思？ 他们在执行的不同部分有什么价值？ 什么是它的正确性certificate的草图？
很明显，在进入主循环之前，它只是检查普通的0或1元素列表的情况。 在主循环的入口处，我指向最后一个元素（而不是一个过去的结束），列表至less有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个“数字”有很多重新sorting，这使排列“增加”了较小的数量。
那么我们什么时候才能最终“使用” 1 ？ 只有最后3位数字没有更多的排列。
什么时候没有更多的最后3位数字排列？ 最后3位数字按降序排列。
啊哈！ 这是理解algorithm的关键。 当右边的东西按降序排列时，我们只改变一个“数字”的位置， 因为如果它不是按降序排列，那么还有更多排列要去 （也就是说我们可以用更小的数量“增加”排列） 。
现在让我们回到代码：
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陈述的升序基本上是find最右边的地方，那么“右边的所有东西都按降序排列”。
我们再来看一些例子：
... 1 4 3 2 2 1 3 4 ... 2 4 3 1 3 1 2 4 ...
我们看到，当一个数字右边的所有东西都是降序时，我们会find下一个最大的数字，然后把它放在前面 ，然后将其余的数字按升序排列 。
让我们看看代码：
It k = end; while (!(*i < *--k)) /* pass */; iter_swap(i, k); reverse(j, end); return true;
那么，因为右边的东西是按照降序排列的，为了find“下一个最大的数字”，我们只需要从最后一行开始迭代，这在前三行代码中就可以看到。
接下来，我们用“ iter_swap()语句将“下一个最大的数字” iter_swap()前面，然后我们知道数字是第二大的，我们知道右边的数字仍然是以降序排列，升序，我们只需要reverse()它。
gcc实现以字典顺序生成排列。 维基百科解释如下：
以下algorithm在给定排列后按照字典顺序生成下一个排列。 它在原地改变给定的排列。
- 找出最大的索引k，使得a [k] <a [k + 1]。 如果不存在这样的指数，排列是最后的排列。
- find最大的索引l，使得a [k] <a [l]。 由于k + 1是这样一个指标，所以l被很好地定义并且满足k <1。
- 用a [l]交换a [k]。
- 反转从[k + 1]到最后一个元素a [n]的序列。
Knuth在“艺术计算机程序devise”第7.2.1.2和7.2.1.3节深入介绍了这种algorithm及其概括。 他称之为“algorithmL” – 显然它可以追溯到13世纪。
下面是使用其他标准库algorithm的完整实现：
template <typename I, typename C> // requires BidirectionalIterator<I> && StrictWeakOrdering<C, ValueType<I>> 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 sorted_end = std::is_sorted_until(rbegin, rend, comp); bool has_greater_permutation = (sorted_end != rend); if (has_greater_permutation) { std::iter_swap( sorted_end, std::upper_bound(rbegin, sorted_end, *sorted_end, comp)); } std::reverse(rbegin, sorted_end); return has_greater_permutation; } template <typename I> // requires BidirectionalIterator<I> && TotallyOrdered<ValueType<I>> bool my_next_permutation(I begin, I end) { return my_next_permutation( begin, end, std::less<typename std::iterator_traits<I>::value_type>{}); }
演示
使用<algorithm>在cppreference上有一个自我解释的可能的实现。
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。
