组合数学中的求后续排列问题

算法思想:
从自然顺序123…n开始,按照字典顺序依次构造集合{1, 2, …, n}的所有全排列,由先序排列构造后续排列的算法如下:
对 p1p2…pn 从右向左扫描,找出比右邻数字小的第1个数pi
对 p1p2…pn 从右向左扫描,找出比 pi 大的第一个数 pj
将 pi 和 pj 互换得 p1p2…pi-1 pj pi+1…pj-1 pi pj+1…pn
将新得到的排列记为b1b2…bn ,则需将该排列中的 bi+1 到 bn 部分的顺序逆转,得b1b2…bn…bi+1

例题:
求839647521的后序排列
1 找出比右边数字小的第一个数“ 839647521”
2 在“4”的右边找出比“4”大的最小的数“839647521”
3 将“4”和“5”对调,成为839657421
4 再将“5”后面的序列翻转,成为839651247

上一篇:PN结


下一篇:C语言中特殊的指针[使用禁忌]