std::next_permutation实现说明
std::next_permutation实现说明
提问于 2012-07-14 18:37:48
我很好奇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个元素长。
主循环的主体中发生了什么？
回答 2
Stack Overflow用户
发布于 2015-09-21 20:36:05
下面是一个使用其他标准库算法的完整实现：
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;
}Stack Overflow用户
发布于 2015-09-21 20:58:21
在使用<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。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/11483060
复制相关文章
相似问题