[理学]15排列的生成算法.ppt

1.5 排列的生成算法 1.5.1 翻转法 1.5.2 换位法 1.5.3 序数法 1.5.4 字典序法 1.5.1 翻转法 一 基本思想 {1,2}的排列 {1} 1 {1,2,3}的排列 {1,2} 12 21 1.5.1 翻转法 {1,2,3,4}的排列 {1,2,3} 123 231 312 213 132 321 1.5.1 翻转法 上述归纳描述已明确对任意正整数n，生成集合{1,2,…,n}的所有排列的系统过程。其中 (1)第一个排列为12…(n－1)n，最后一个排列为n(n－1)…21 (2)当Pn≠n时，排列PnPn-1…P2P1的直接后继排列为Pn-1Pn-2…P2P1Pn 1.5.1 翻转法 二 计算机实现 从排列P4P3P2P1＝ 1234 开始 1234 (当前排列P4≠4,翻转当前排列前1位到该排 列尾部) 2341 (同上) 3412 (同上) 4123 (当前排列P4＝4,P3≠3,翻转当前排列前2位 到该排列尾部) 1.5.1 翻转法 2314 (当前排列中P4≠4，翻转当前排 列前1位到该排列尾部) 3142 (同上) 1423 (同上) 4231 (当前排列中P4＝4，P3≠3，翻转 当前排列前2位到该排列尾部) 1.5.1 翻转法 3124 (当前排列中P4≠4，翻转当前排 列前1位到该排列尾部) 1243 (同上) 2431 (同上) 4312 (当前排列P4＝4,P3＝3,P2≠2, 翻 转当前排列前3 位到该排列尾部) 1.5.1 翻转法 2134 (当前排列中P4≠4，翻转当前排列 前1位到该排列尾部) 1342 (同上) 3421 (同上) 4213 (当前排列P4＝4,P3≠3,翻转当前排 列前2位到该排列尾部) 1.5.1 翻转法 1324 (当前排列P4≠4，翻转当前排列 前1位到该排列尾部) 3241 (同上) 2413 (同上) 4132 (当前排列P4＝4,P3≠3,翻转当前 排列前2位到该排列尾部) 1.5.1 翻转法 3214 (当前排列P4≠4，翻转当前排列前1位到 该排列尾部) 2143 (同上) 1432 (同上) 4321 (当前排列P4＝4,P3＝3,P2＝2,P1＝1,算法 终止) 注意，翻转最后排列4321前4位到该排列尾部得第一个排列1234，因此算法是循环的。 1.5.1 翻转法 定理1.5.1 按上述归纳描述，集合{1,2,…,n}的任一排列所处位置数为 n!－ － －…－ － 其中常数ai(i＝2,3,…,n－1,n)为该排列中排在数i前和数i+1后的小于i的元素的个数(注意，常数an即为该排列中排在数n前且小于n的元素的个数，因该排列中无数n+1)。 1.5.1 翻转法 例如，集合{1,2,3,4,5}的排列45312所处位置数为 5!－ － － － ＝ 5!－ － － － ＝44 1.5.1 翻转法 三 算法描述 生成集合{1,2,…,n}的所有排列的翻转算法 从排列PnPn-1…P2P1 ＝ 12…n开始，当 PnPn-1…P2P1 ≠ n(n－1)…21时，做： (1)从左向右扫描找出使得Pi≠i的最大整数 i(1≤i≤n) (2)PnPn-1…P2P1＝Pi-1Pi-2…P2P1PiPi+1…Pn-1Pn 1.5.1 翻转法 定理1.5.2 上面描述的算法，对每个正整数n产生集合{1,2,…,n}的n!个不同排列。 证明 (1)算法用于n＝1,2时，定理成立 (2)假设算法用于每个正整数k(k≤n－1)， 产生集合{1,2,…,k}的k!个不同排列 1.5.1 翻转法 设当前排列为PnPn-1…Pk+1PkPk-1…P2P1(Pn＝n, Pn-1＝n－1,…,Pk+1＝k＋1, Pk≠k)。则PkPk-1…P2P1是集合{1,2,…,k}的一个排列，且其直接后继是Pk-1Pk-2…P2P1Pk。于是(k＋1)PkPk-1…P2P1与Pk-1Pk-2…P2P1Pk(k＋1)是集合{1,2