英文:
What is the internal of `next_permutation()` function in c++
问题
最近我解决了一个排列的问题。然后我搜索了一个库函数来解决这个问题。我找到了next_permutation函数。使用这个函数，我解决了问题。我搜索了很多以找出函数的内部工作原理，但我没有找到好的信息源。
vector<vector<int>> permute(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> v;
do{
v.push_back(nums);
}while(next_permutation(nums.begin(), nums.end()));
return v;
}
我想了解这个函数的内部工作原理。如果有人了解，请分享一下函数的代码。
英文:
Recently I solved a problem of permutation. Then I searched for library function for solve a the problem. I found next_permutation function. Using the function I Solved the problem. I searched a lot to find out the internal of the function but I did not find good sources.
vector<vector<int>> permute(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>>v;
do{
v.push_back(nums);
}while(next_permutation(nums.begin(), nums.end()));
return v;
}
I want to know about the internal of the function. If anyone know about it , please share a code for the function.
答案1
得分: 3
这是来自libstdc++的实现（与SGI STL中的相同），稍作简化和清理以提高可读性：
template<typename BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last)
{
if (first == last)
return false;
BidirectionalIterator i = first;
++i;
if (i == last)
return false;
i = last;
--i;
for(;;)
{
BidirectionalIterator ii = i;
--i;
if (*i < *ii)
{
BidirectionalIterator j = last;
while (!(*i < *--j)) {}
std::swap(*i, *j);
std::reverse(ii, last);
return true;
}
if (i == __first)
{
std::reverse(first, last);
return false;
}
}
}
这是一个众所周知的算法（"Algorithm L"），请参阅D.E.Knuth的计算机编程艺术第4A卷中的第7.2.1.2节生成所有排列。
该算法的思想是：对于当前排列，在右侧找到最长的递减子序列{...ap ≤ ai > aj > ... > ak}，找到范围[i, k]内具有最大可能f的下一个前置元素af > ap，交换af和ap，然后将剩余元素按升序排列，即反转子序列{ai...ap...ak}。
英文:
Here is the implementation from libstdc++ (same as in SGI STL) simplified and cleaned up a little bit for readability:
template<typename BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last)
{
if (first == last)
return false;
BidirectionalIterator i = first;
++i;
if (i == last)
return false;
i = last;
--i;
for(;;)
{
BidirectionalIterator ii = i;
--i;
if (*i < *ii)
{
BidirectionalIterator j = last;
while (!(*i < *--j)) {}
std::swap(*i, *j);
std::reverse(ii, last);
return true;
}
if (i == __first)
{
std::reverse(first, last);
return false;
}
}
}
This is a well-known algorithm ("Algorithm L"), see Sec. 7.2.1.2 Generating all permutations in The art of computer programming. Vol. 4A: Combinatorial algorithms, Part 1 by D.E.Knuth.
Idea of the algorithm: for the current permutation, find the longest decreasing subsequence on the right, {...ap ≤ ai > aj > ... > ak}, find the next front element af > ap with the largest possible f in the range [i, k], swap af and ap, and then put the remaining elements in the ascending order, i.e. reverse the subsequence {ai...ap...ak}.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论