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。