我很好奇 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()));
我的问题是:
while (!(*i < *--k))
/* Iterating linearly */;
为什么我们不能进行二进制搜索而不是简单的线性迭代,因为 [i+1 , end) 中的序列是降序排列的?这将提高搜索效率。 “algorithm.h”中的标准函数怎么能忽略这种导致更好的性能和效率的事情呢?请有人解释...
最佳答案
您很少会有一个数组要置换超过 15 个元素(实际上甚至更少),因为它需要您处理 15 个! > 10^12 种不同的排列。对于具有如此小尺寸的数组,二分搜索的效率低于简单的线性搜索。
关于c++ - std::next_permutation Implementation Explanation 似乎有点低效?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17212596/