1、碰到next_permutation(permutation:序列的意思)
今天在TC上碰到一道简单题(SRM531 - Division Two - Level One),是求给定数组不按升序排列的最小字典序列(Sequence of numbers A is lexicographically smaller than B if A contains a smaller number on the first position on which they differ)。
解法很简单,就是将数组排序(升序),然后从尾到头找到第一个可以交换的位置(因为可能有重复的数字)。
最后看别人的解法,排序后,用了STL中的一个函数next_permutaion,直接求到第一个不按升序排列的序列。
2、next_permutation实现原理
在《STL源码解析》中找到了这个函数,在此也简单叙述一下原理:
在STL中,除了next_permutation外,还有一个函数prev_permutation,两者都是用来计算排列组合的函数。前者是求出下一个排列组合,而后者是求出上一个排列组合。所谓“下一个”和“上一个”,书中举了一个简单的例子:对序列 {a, b, c},每一个元素都比后面的小,按照字典序列,固定a之后,a比bc都小,c比b大,它的下一个序列即为{a, c, b},而{a, c, b}的上一个序列即为{a, b, c},同理可以推出所有的六个序列为:{a, b, c}、{a, c, b}、{b, a, c}、{b, c, a}、{c, a, b}、{c, b, a},其中{a, b, c}没有上一个元素,{c, b, a}没有下一个元素。
next_permutation的函数原型如下:
template<class BidirectionalIterator>
bool next_permutation(
BidirectionalIterator _First,
BidirectionalIterator _Last
);
template<class BidirectionalIterator, class BinaryPredicate>
bool next_permutation(
BidirectionalIterator _First,
BidirectionalIterator _Last,
BinaryPredicate _Comp
);
对于第二个重载函数的第三个参数,默认比较顺序为小于。如果找到下一个序列,则返回真,否则返回假。
函数实现原理如下:
在当前序列中,从尾端往前寻找两个相邻元素,前一个记为*i,后一个记为*ii,并且满足*i < *ii。然后再从尾端寻找另一个元素*j,如果满足*i < *j,即将第i个元素与第j个元素对调,并将第ii个元素之后(包括ii)的所有元素颠倒排序,即求出下一个序列了。
代码实现如下:
template<class 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 = lase;
while(!(*i < *--j));
iter_swap(i, j);
reverse(ii, last);
return true;
}
if(i == first) {
reverse(first, last); //全逆向,即为最小字典序列,如cba变为abc
return false;
}
}
}
prev_permutation实现类似,就是反向查找
3、使用next_permutation
思考问题,序列{a, d, c, e, b}的下一个序列是什么呢?请利用前面的分析推出答案,并用代码验证。
我这里分别用数组和vector来表示序列,用next_permutation得到下一个序列(编译环境:Dev-C++):
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void TestArray()
{
char chs[] = {'a', 'd', 'c', 'e', 'b'};
int count = sizeof(chs)/sizeof(char);
next_permutation(chs+0, chs + count);
printf("TestArray:\n");
for(int i = 0; i < count; i++) {
printf("%c\t", chs[i]);
}
printf("\n");
}
void TestVector()
{
char chs[] = {'a', 'd', 'c', 'e', 'b'};
int count = sizeof(chs)/sizeof(char);
vector<char> vChs(chs, chs + count);
next_permutation(vChs.begin(), vChs.end());
printf("TestVector:\n");
vector<char>::iterator itr;
for(itr = vChs.begin(); itr != vChs.end(); itr++) {
printf("%c\t", *itr);
}
printf("\n");
}
int main(int argc, char *argv[])
{
TestArray();
printf("\n");
TestVector();
system("PAUSE");
return EXIT_SUCCESS;
}
运行结果:
4、小结
用next_permutation和prev_permutation求排列组合很方便,但是要记得包含头文件#include <algorithm>。
虽然最后一个排列没有下一个排列,用next_permutation会返回false,但是使用了这个方法后,序列会变成字典序列的第一个,如cba变成abc。prev_permutation同理。
分享到:
相关推荐
一:next_permutation(start,end,//cmp) 使用默认排序方法:按照字典序从小到大 int arr[3]={1,2,3}; do{ for(int num:arr){ cout<<num<< ; } cout<<endl; }while(next_permutation...
最低加油次数 ...Next_permutation Stack, trick trick TOP 类似斐波拉契,一层层处理 字符串处理 TOP 完全背包 dfs Trick TOP next_permutation dfs or stl next_permutation dfs or stl TOP 排序后的字符串作
STL介绍 3 1、STL简介 3 2、算法 3 3、容器 3 4、迭代器 4 5、使用注意 4 ...18. next_permutation / prev_permutation 36 19. power 37 20. heap operations 38 21. min / max / swap 39 22. numeric_limits 39
使用c++库函数实现全排列,注意next_permutation,使用do{}while()循环
23.28 下一排列组合next_permutation 406 23.29 上一排列组合prev_permutation 409 23.30 本章小结 411 第24章 数值算法 412 24.1 递增赋值iota 412 24.2 元素求和accumulate 413 24.3 两序列元素内积...
23.28 下一排列组合next_permutation 406 23.29 上一排列组合prev_permutation 409 23.30 本章小结 411 第24章 数值算法 412 24.1 递增赋值iota 412 24.2 元素求和accumulate 413 24.3 两序列元素内积...
全排列算法有两个比较常见的实现:递归排列和字典序排列。 (1)递归实现 从集合中依次选出每一个元素,作为排列的第一个...这种方式实现得到的所有排列是按字典序有序的,这也是C++ STL算法next_permutation的思想
常见得全排列有三种解决方案,for循环穷举,stl摸板函数next_permutation,还有DFS深度优先搜索,当我们遇到带有重复的字符串时应该考虑除去重复的部分。
6.7.5 next_permutation 380 6.7.6 prev_permutation 382 6.7.7 random_shuffle 383 6.7.8 partial_sort / partial_sort_copy 386 6.7.9 sort 389 6.7.10 equal_range(应用于有序区间) 400 6.7.11 inplace_...
23.28 下一排列组合next_permutation 406 23.29 上一排列组合prev_permutation 409 23.30 本章小结 411 第24章 数值算法 412 24.1 递增赋值iota 412 24.2 元素求和accumulate 413 24.3 两序列元素内积...
高铁 英文 |介绍GoSTL是go的数据结构和算法库,旨在提供类似于C++ STL的功能,但功能更强大。 结合go语言的特点,大部分数据结构都实现了goroutine-safe。 创建对象时,可以通过配置参数指定是否开启。功能列表数据...
6.7.5 next_permutation 380 6.7.6 prev_permutation 382 6.7.7 random_shuffle 383 6.7.8 partial_sort / partial_sort_copy 386 6.7.9 sort 389 6.7.10 equal_range(应用于有序区间) 400 6.7.11 inplace_...
STL算法常用函数:分隔组合:next_permutation()是检索当前范围内的划分,并重新排序为下一个替换,leetcode 556下一个元素元素III prev_permutation()是替换指定范围内的序列重新排列它重新排序为上一个序列。...
我只是将 C++ STL 函数 next_permutation 包装在 Mex 中。 若要使用,请先使用“ mex nextperms.cpp”为您的系统编译。 有关文档,请参阅 nextperms.m 和 nextperms_example_script.m。 典型的用例是您需要遍历...
34.28 next_permutation 34.29 nth_element 34.30 partial sort 34.31 partial sort_copy 34.32 partition 34.33 pop_heap 34.34 prev_permutation 34.35 push_heap 34.36 random_shuffle 34.37 remove,remove_if,...
leetcode中国 LeetCode | LuoGu 题型记录 P1980 计数问题 (数位dp, 朴素算法) P1047 校门外的树 (线段树, ...全排列问题(next_permutation, dfs(最主要需要记住,置位后需要清0(f[i]=0))) P3392 涂国旗(组合) P23
++较少使用的功能(例如隐藏在STL中的算法,例如std :: next_permutation )也可以提高我的整体编码技能。 听起来像是双赢的局面... “但是您不应该发布解决方案!” 项目Euler鼓励您不要发布解决方案。 我有不同的...
《Linux多线程服务端编程:使用muduo C++网络库》主要讲述采用现代C++在x86-64 Linux上编写多线程TCP网络服务程序的主流常规技术,重点讲解一种适应性较强的多线程服务器的编程模型,即one loop per thread。...