基于逆序列的字典序改进算法.PDFVIP

基于逆序列的字典序改进算法 * † 孔涛 李文焯 清华大学计算机科学与技术系，北京 100084 摘要：字典序法是生成全排列的经典算法。本文在对字典序法进行分析的基础上，提出 了一种基于逆序列的改进字典序全排列生成算法。通过与传统的四种全排列生成算法进 行对比，本文方法可以大大提高全排列的生成效率。 关键词：全排列；字典序；逆序列 1 引言 全排列问题是组合数学中的经典问题。全排列在解决很多问题中作为基础算法出 现。目前主要的全排列生成算法有字典序法、递增进位制数法、递减进位制数法和 邻位对换法（SJT）[1]。在这四种算法中，字典序法在实际应用中最为普遍。字典序 法借鉴字典中字符的排列顺序，在应用中更为直观。C++ 标准程序库中有两个函数 next_permutation, prev_permutation，可以生成字典序排列。因此，如何更快地利用字典 序法生成全排列一直是科研工作者的目标。 2 字典序法 2.1 算法流程 字典序法生成全排列的算法如下，设 是 − 的全排列, 下一个排 列的生成算法为 • 从排列的右端开始，找出第一个比右边数字小的数字的序号 （ 从左端开始计 算），即 max{ | }。 • 在 的右边的数字中，找出所有比 大的数中最小的数字 ，即 max{ | } （右边的数从右至左是递增的，因此 是所有大于 的数字中序号最大者）。 *通讯作者：kt14@mails.tsinghua.edu.cn †li-wz14@mails.tsinghua.edu.cn • 对换 ， 。 • 再将 倒转得到排列 ′ ， 这就是排列 的下一个下一个排列。 要生成 − 的全排列，那么算法的初始序列为 ，终止序列为 − 。 2.2 算法的正确性 大小的定义： 我们首先给出比较两个序列 和 假设 和 的前 个数均相同，若 ，则 ，若 ，则 。特别的，若 ，则 。 要证明这个算法的正确性，我们只要证明生成的下一个排序是恰好比当前排列大的 最小的一个序列即可。 • 第一步找出的序列 是一个递减序列 • 第二步和第三步得到 。因为 ，这就保证了新的序列大于原来的序列。 • 第四步通过将 后边的序列逆转（原序列是递增序列），从而得