1.5排列生成算法.pptVIP

1.5 排列的生成算法 生成集合{1,2,…,n}的所有排列的算法 (1)算法结果须是一个表，该表含{1,2,…,n} 的每个排列，且每个排列只出现一次。 (2)仅使用当前排列一次一个地生成下一个排 列，且要求不保留所有排列的列表就能够 简单地用后面的排列覆盖当前的排列。 (3)算法必须是循环的。 1.5 排列的生成算法 1.5.1 翻转法 1.5.2 换位法 1.5.3 序数法 1.5.4 字典序法 1.5.1 翻转法 (一) 基本思想 构造集合{1,2,…,n}的所有排列可分两步： (1)将n插入{1,2,…,n－1}的每个排列后，得 到{1,2,…,n}的(n－1)！个不同排列； (2)选定(1)的一个排列，依次将该排列的前i 位(i＝0,1,2,…,n－1)调到该排列的尾部， 得{1,2,…,n}的n个不同排列。 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开始，从左向右找第一个pk≠k，设pk所处位置数为i，翻转前i位到尾部 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 翻转法 证明设Pn-1Pn-2…P2P1为{1,2,…,n－1}第t个排 Pn-1Pn-2…P2P1n (t－1)n＋1＝tn－(n－1)＝tn－an Pn-2Pn-3…P2P1nPn-1 tn－n＋2＝tn－an Pn-3…P2P1nPn-1Pn-2 tn－n＋3＝tn－an W(n)＝W(n－1)n－an P1nPn-1Pn-2…P3P2 tn－n＋n－1＝tn－an nPn-1Pn-2…P2P1 tn－n＋n＝tn－an 1.5.1 翻转法 例如，{1,2,3,4}的排列3241所处位置数为 4!－ － － ＝4!－ － － ＝18 例如，{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与Pk-1Pk-2…P2P1Pk 集合{1,2,…,k}相邻前后排列 (k＋1)PkPk-1…P2P1与Pk-1Pk-2…P2P1Pk(k