今天想学学全排列的非递归实现,但是搜索了半天,都是转载的同一篇文章,这篇文章的规律我还是没看懂。
想到c++的STL里有一个next_permutation()可以实现产生比当前序列大一点的下一个序列。
通过这种方法,也可以实现全排列的非递归实现。
STL源码下载:http://www.sgi.com/tech/stl/download.html
next_permutation()的原函数位于:stl_alog.h里面
内容如下:
// next_permutation and prev_permutation, with and without an explicitly
// supplied comparison function.
template <class _BidirectionalIter>
bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
__STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator);
__STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type,
_LessThanComparable);
if (__first == __last)
return false;
_BidirectionalIter __i = __first;
++__i;
if (__i == __last)
return false;
__i = __last;
--__i;
for(;;) {
_BidirectionalIter __ii = __i;
--__i;
if (*__i < *__ii) {
_BidirectionalIter __j = __last;
while (!(*__i < *--__j))
{}
iter_swap(__i, __j);
reverse(__ii, __last);
return true;
}
if (__i == __first) {
reverse(__first, __last);
return false;
}
}
}
基本思想如下:
从最后每相邻的两个进行比较,如果有前面一个比后面的小(i为较小位置,ii,为较大位置),那么此时一定存在一个排列比当前的大,然后是怎么产生这下一个排列。应该找这个较小的数的后面从最后开始比它大的第一个数,将它换到当前较小的位置上,然后将较大数ii到最后进行逆序。这样就产生了下一个排列。原理类似于,找到下一个较大的作为开始位的数,然后将后面的数字从最小开始即升序,例如原来为4653转换后为:5346
next_permutation()
{
if no element || only one element
return false;
i = last_element_ptr
while(true)
{
ii = i; // the element before i
--i;
if *i < *ii // then there must be a sequence to change
{
j = last_element_ptr
while( !(*i<*--j) //find the first element from tail to head
{} //which is bigger than *i
swap(i, j) // swap the elements which i and j point to.
reverse(ii, last_element_ptr) // reverse the array
return true;
}
if i == first_element_ptr // if we to the head of the array, so no permutation
{
reverse(first_element_ptr, last_element_ptr)
return false
}
}
}
从stl的next_permutation源码中我们看到,对于一个已经是最大权值的序列(即没有下一个比当前值大的排列),虽然返回值是false,但是它仍就将序列进行了逆序,例如对4321使用next_permutation后,序列变为1234.
看来读读久经考验的源代码是大有好处的。
由此,我们就可以实现非递归的全排列了。呵呵 ,不用多说了吧。
分享到:
相关推荐
一:next_permutation(start,end,//cmp) 使用默认排序方法:按照字典序从小到大 int arr[3]={1,2,3}; do{ for(int num:arr){ cout<<num<< ; } cout<<endl; }while(next_permutation...
stlshow_stl分层_STL分层_stlmatlab_STL切片_stl分层_源码.rar.rar
stlshow_stl分层_STL分层_stlmatlab_STL切片_stl分层.zip
用于三维光学形貌扫描完成后,生成的stl文件的读取,并形成俯视投影云图
C++读取STL文件,输出所有三角形的顶点坐标
上传stl文件,等到模型的体积、尺寸等参数
最新的STL源码,最新的STL源码,最新的STL源码
西门子S7-300语句表 STL 实例源代码
用于STL文件读取与显示的C语言程序,简单方便实用。
#ifndef __SGI_STL_INTERNAL_ALGOBASE_H #define __SGI_STL_INTERNAL_ALGOBASE_H #ifndef __STL_CONFIG_H #include <stl_config.h> #endif #ifndef __SGI_STL_INTERNAL_RELOPS #include <stl_relops.h> #endif #...
VC++利用动态连接库开发的读取STL格式文件的界面,可鼠标点选,旋转物体,有需要的朋友可以下载
读取 点云数据 STL 文件 分块化编程
STL文件读取程序(Matlab):可以将ASCII格式的的STL文件中的数据点信息及网格拓扑信息读出,并显示在屏幕上
STL源码_侯捷注释,相信大家都有看过侯捷的STL的源码解析那本书吧。 这是STL的注释
很多做三维重建的开发人员都需要读取三维数据,这个程序实现了读取三维数据文件(stl文件)的函数,并用opengl显示出来了,很有参考价值的,其中有函数readstlfile就是实现了从stl文件中读取三角面片的数据。
STL学习教程,
在matlab实现STL分层,自定义厚度,参考意义
基于VC++和OpenGL的STL文件读取显示STL是三维模型常用的文件格式。对STL文件进行读取和显示,是对模型进行后续操作的前提。在对STL文件格式进行详细分析的基础上,以VC+-I-作为开发平台
看STL文件的小软件,可以自由的实现旋转,等功能,现在只是一小部分,以后会发后面的
STL在liunx下的源代码文件,可以在Linux下安装,也可以直接阅读源码来学习STL编程