1、 多重集全排列算法的研究 李智佳 刘志福 朱颖 张志炜主要工作搜索上百篇论文,完成众多论文的阅读整理工作提出了TWDRI算法,目前已知的速度最快的算法在排列算法领域,第一次提出了平均时间测试模型,并进行了大量的模拟比较,证明TWDRI是速度最快的算法优化了Knuth算法,将其速度提高100%汇编分析工作 目录项目介绍1TWDRI算法2模拟比较3汇编分析4项目总结5项目介绍 概念,初始工作,项目背景制约发展的瓶颈N 排列的数量 Million/sec Billion/sec Trillion/sec10 362880011 39916800 Seconds12 479001600 minutes
2、13 6227020800 Hours Seconds14 87178291200 Day Minute15 1307674368000 Weeks Minutes16 20922789888000 Months Hours Seconds17 355687428096000 years Days Minutes18 6402373705728000 Months Hours19 121645100408832000 years Days20 2432902008176640000month漫长的等待微不足道的时间项目概念介绍问题:产生N个元素所有的N!个排列例如集合 , , 项目概念介绍是多
3、重集 集合 有重 出 的元素的集合 如: , , , , , 是 排列 集合 有重 出 的元素的集合的排列 如 项目概念介绍问题:多重集的全排列例如多重集0,1,1,2的排列:(1)0112 (7)1120(2)0121 (8)1201(3)0211 (9)1210(4)1012 (10)2011(5)1021 (11)2101(6)1102 (12)2110 多 的发展 理 排列 重 的数 出 的集合的算法大多数理多重集排列的算法比较 算法的一大是currency1多算法 有“并fifl 的数模拟比 出了一论,”的要一个比较全 fi 平的算法比较法 的所 提出了一平均时间测试模型, currency1 的算法的比较问题 ”是次论文 的一个 模型的 :一 所有 在个 上”要进行比较高 模型 作 ,算法