当前位置:  编程技术>c/c++/嵌入式

使用C++实现全排列算法的方法详解

    来源: 互联网  发布时间:2014-10-15

    本文导语:  代码如下:不论是哪种全排列生成算法,都遵循着“原排列”→“原中介数”→“新中介数”→“新排列”的过程。其中中介数依据算法的不同会的到递增进位制数和递减进位制数。关于排列和中介数的一一对应性的证明我们...

代码如下:

不论是哪种全排列生成算法,都遵循着“原排列”→“原中介数”→“新中介数”→“新排列”的过程。

其中中介数依据算法的不同会的到递增进位制数和递减进位制数。

关于排列和中介数的一一对应性的证明我们不做讨论,这里仅仅给出了排列和中介数的详细映射方法。



· 递增进位制和递减进位制数 
所谓递增进位制和递减进位制数字是指数字的进制随着数字位置的不同递增或递减。通常我们见到的都是固定进制数字,如2进制,10进制等。m位n进制数可以表示的数字是m*n个。而m位递增或递减进位制数则可以表示数字m!个。例如递增进位制数4121,它的进制从右向左依次是2、3、4、5。即其最高位(就是数字4那位)最大值可能是4;第三高位最大可能是3;第二高位最大可能是2;最末位最大可能是1。如果将4121加上1的话,会使最末位得到0,同时进位;第二位的2与进位相加,也会得到0,同时进位;第三位的1与进位相加得到2,不再进位。最终得到结果是4200。递减进位制的道理是一样的,只不过进制从右向左依次是9、8、7、6……,正好与递增进位制相反。很明显,递减进位制的一个最大的好处就是加法不易进位,因为它在进行加法最频繁的末几位里(最右边)进制比较大。

接下来要了解的是递增进位制、递减进位制数和其序号的关系。递增、递减进位制数可以被看作一个有序的数字集合。如果规定递增进位制和递减进位制数的0的序号是十进制0,递增进位制数的987654321和递减进位制数的123456789对应十进制序号362880(即9!),则可以整理一套对应法则。其中,递增进位制数(a1 a2 a3 a4 a5 a6 a7 a8 a9)为:

a1*9! + a2*8! + ….+ a8*2! + a9*1! = 序号

例如序号100的递增进位制数就是4020,即4*4!+ 0*3!+ 2*2!+ 0*1!=100。将一个序号转换成其递增进位制数首先需要找到一个比序号小的最大阶乘数(即1、2、6、24、120、720……),对其进行整数除得到递增进位制的第一位;将除法的余数反复应用这个方法(当然,之后选择的余数是小一级的阶乘数),直到余数为0。

递减进位制数(a1 a2 a3 a4 a5 a6 a7 a8 a9)为:

(((((((((a1 * 1 + a2) * 2 + a3) * 3 + …… + a7) * 8 + a8) * 9 + a9= 序号 

例如序号100的递减进位制数就是131(a7 a8 a9, 即从后对齐),即 (1*8 + 3)*9 + 1 = 100。将一个序号转换成其递减进位制数,需要对序号用9取余数,就可以得到递减进位制的最末位(这点和递增进位制先算出最高位相反)。用余下的数的整数除结果重复此过程(当然,依次对8、7、6……取余),直到余数为0。 

关于递增进位制和递减进位制需要注意的重点:一是其加减法的进位需要小心;二是序号和数字的转换。除了100之外,常见的转换有:999的递增数是121211,递减数是1670;99的递增数是4011,递减数是130。大家可以以此为参考测试自己是否真正理解了计算的方法。下文将省略递增进位制或递减进位制的详细计算过程。

从现在开始我们将详细介绍六种排列生成算法。具体的理论介绍将被忽略,下文所注重的就是如何将排列映射为中介数以及如何将中介数还原为排列。

我全部以求839647521的下100个排列为例。

· 递增进位排列生成算法
映射方法:将原排列按照从9到2的顺序,依次查看其右侧比其小的数字的个数。这个个数就是中介数的一位。例如对于原排列839647521。9的右侧比9小的数字有6个,8的右侧比8小的数字有7个,7的右侧比7小的数字有3个,……2的右侧比2小的数字有1个。最后得到递增进制中介数67342221。(此中介数加上100的递增进制数4020得到新的中介数67351311)

还原方法:我们设新中介数的位置号从左向右依次是9、8、7、6、5、4、3、2。在还原前,画9个空格。对于每一个在位置x的中介数y,从空格的右侧向左数y个未被占用的空格。在第y+1个未占用的空格中填上数字x。重复这个过程直到中介数中所有的位都被数完。最后在余下的最后一个空格里填上1,完成新排列的生成。以新中介数67351311为例,我给出了详细的恢复步骤。其中红色数字代表新填上的数字。最后得到新排列869427351。

代码如下:

void next_Permutations_by_increDecimal(int dataArr[],int size){
 int i;
 int *resultArr = new int[size];
 int index = 0;
 map::iterator iter;
    //第一步 求出中介数
 //由大到小,得到并记录当前排列中,数字i的右边比其小的数的个数
    map agentMap;
 for(i=0; i

    
 
 

您可能感兴趣的文章:

  • C++ I/O 成员 tellg():使用输入流读取流指针
  • 为什么使用了-l但 仍然不能使用C++类库
  • C++ I/O 成员 tellp():使用输出流读取流指针
  • linux下的C++编译器怎样使用?
  • windows下tinyxml.dll下载安装使用(c++解析XML库)
  • 各位在Unix下开发,使用哪种c++编译器?
  • tcmalloc内存泄露优化c++开源库下载,安装及使用介绍
  • 在Linux下怎么使用C++啊?gcc是C吧?
  • c++类库Boost::bimap(双向映射)介绍及使用实例
  • 请问linux下可以使用c++么?
  • TinyXML(c++下操作xml的库)介绍,下载地址及使用代码举例
  • redhat linux平台下文件正在使用判别C++?
  • 在Python中使用SWIG调用C和C++程序
  • 如何编译一个使用了QT或KDE类的C++程序
  • c++ stl multimap基本操作使用技巧详细介绍
  • Linux下使用C++互斥访问文件+消息队列
  • 请问怎么样使用 Linux下的C++集成开发环境。
  • 使用c++编写gtk程序
  • putty下如何使用gcc编译c或c++程序的资料
  • 大家在UNIX下写程序使用C++么?
  • 是不是只有C++才可以使用STL?
  • 使用java jdk中的LinkedHashMap实现简单的LRU算法
  • 操作系统的使用的处理死锁的算法
  • 算法之排序算法的算法思想和使用场景总结
  • 请问linux中,有没有现成的md5算法可以使用?
  • 使用swap指令和Test and set指令设计一个解决N个进程互斥问题的算法
  • java不可逆加密算法之md5加密算法使用示例
  • 使用递归算法求第30位数的值
  • python基础教程之python消息摘要算法使用示例
  • 浙ICP备11055608号-3 iis7站长之家
  • rsa加密算法使用示例分享
  •  
    本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • linux下top命令详解包括top命令参数使用及结果(virt,res,shr)排序举例说明
  • 如何在Linux下使用脚本实现程序的自动重启!望各位详解!
  • linux top命令详解以及top命令的各项使用技巧详细说明
  • c# 空合并运算符“??”的使用详解
  • 在android开发中尽量不要使用中文路径的问题详解
  • 深入SQLServer中ISNULL与NULLIF的使用详解
  • MYSQL 批量替换之replace语法的使用详解
  • 汇编语言rep movsd 的使用详解
  • 使用SQL Server判断文件是否存在后再删除(详解)
  • 深入C#中使用SqlDbType.Xml类型参数的使用详解
  • 基于C语言fflush()函数的使用详解
  • 基于C++字符串替换函数的使用详解
  • Android开发笔记之:一分钟学会使用Logcat调试程序的详解
  • 深入分析Java内存区域的使用详解
  • Python Deque 模块使用详解
  • c语言中位字段与结构联合的组合使用详解
  • C#中is与As运算符号的使用详解
  • 基于DateTime.ParseExact方法的使用详解
  • 使用DateTime的ParseExact方法实现特殊日期时间的方法详解
  • 从汇编看c++的默认析构函数的使用详解
  • oracle合并列的函数wm_concat的使用详解
  • Python不使用print而直接输出二进制字符串
  • 在测试memset函数的执行效率时,分为使用Cash和不使用Cash辆种方式,该如何控制是否使用缓存?
  • Office 2010 Module模式下使用VBA Addressof
  • 求ibm6000的中文使用手册 !从来没用过服务器,现在急需使用它,不知如何使用! 急!!!!!
  • sharepoint 2010 使用STSNavigate函数实现文件下载举例
  • 请问:在使用oracle数据库作开发时,是使用pro*c作开发好些,还是使用库函数如oci等好一些啊?或者它们有什么区别或者优缺点啊?
  • 使用libpcap读取tcpdump抓取的文件并解析c代码实例
  • 急求结果!!假设一个有两个元素的信号量集S,表示了一个磁带驱动器系统,其中进程1使用磁带机A,进程2同时使用磁带机A和B,进程3使用磁带机B。
  • c/c++预处理命令预#,##使用介绍
  • c#中SAPI使用总结——SpVoice的使用方法




  • 特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3