n 阶排列中相同逆序数的排列个数递推算法
Ξ
晏建学 ,王云秋
(
云南财贸学院 计算机科学系 ,云南 昆明 650221
)
摘 要
用生成函数
(
母函数
)
讨论了 n 阶排除中具有相同逆序数 k 的排列个数 d
(
n , k
)
的新递推公式 ,将 d
(
n , k
)
的计算
转化成其生成函数的计算 ,从而得到一个可以用计算机完成的算法.
关键词 :
n 阶排列;逆序数 k ;排列个数 d
(
n , k
)
;递推公式;生成函数
(
母函数
)
G
n
(
x
)
【中图分类号】O12214 【文献标识码】A 【文章编号】1672 —8513
(
2004
)
04 - 0295 - 04
0 引言
逆序数是衡量一个排列无次序程序的一个重要指标. 数{1 ,2 ,3 , …, n - 1 , n} 构成的所有 n 阶排列共有
n !个 ,其中奇、偶排列各半个. 逆序数为 0 的排列只有一个顺序排列
(
1 ,2 ,3 , …, n - 1 , n
)
,逆序数为
n
(
n - 1
)
2
的排列也只有一个 ,那就是全逆序排列
(
n , n - 1 , …,3 ,2 ,1
)
. 在一般情况下 ,
n 阶排列中具有相同逆序数 k
(
0
≤k ≤
n
(
n - 1
)
2
)
排列个数 d
(
n , k
)
≥1. 如何计算每个 d
(
n , k
)
及全体 n 阶排列
(
共 n !个
)
的逆序数的总
和
(
逆序总数
)
呢 ?文献
[1 ]
专门用一节讨论了排列与置换问题. 文献
[2 ]
用构造辅助元素的方法解决了逆序总数
问题. 文献
[1 ]
给出了计算 d
(
n , k
)
的一个递推公式
d
(
n , k
)
= d
(
n - 1 , k
)
+ d
(
n - 1 , k - 1
)
+ d
(
n - 1 , k - 2
)
+ …+ d
(
n - 1 , k -
(
n - 1
) )
用该递推公式计算 d
(
n , k
)
的主要问题是 :计算一个
d
(
n , k
)
需要计算
n 个 d
(
n - 1 , k - i
)
,而计算一个
d
(
n
- 1 , k - i
)
需要再计算
n - 1 个 d
(
n - 2 , k - i - j
)
,如此递推下去 ,计算一个
d
(
n , k
)
需递推
n 层 ,计算 n !
次低阶 d
(
n - p , k - q
)
的值 ,递推层数与 n 同阶 ,递推次数与 n !同阶 ,时间复杂性及空间复杂性太高.
本文通过讨论 d
(
n , k
)
的生成函数
G
n
(
x
)
= d
(
n ,0
)
+ d
(
n ,1
)
·x + d
(
n ,2
)
·x
2
+ …+ d
(
n , k
)
·x
k
+ …+ d
(
n ,
n
(
n - 1
)
2
)
·x
n
(
n- 1
)
2
给出了新的递推公式 G
n
(
x
)
= G
n - 1
(
x
)
·
(
1 + x + x
2
+ …+ x
n - 1
)
使用新的递推公式有 3 个优点 : ①递推 G
n
(
x
)
为多项式时间算法 ,时间复杂性及空间复杂性低;
②递推
G
n
(
x
)
的同时就求出了所有的 d
(
n , k
)
; ③利用 G
n
(
x
)
的性质能够更方便地讨论 d
(
n , k
)
的性质. 老问题 ,
新办法.
1 新递推公式的推导
首先 ,我们通过邻位对换来看一下 n 阶排列中逆序数的构成
(
1 ,2
) (
1 ,3
) (
1 ,4
)
…
(
1 , n - 1
) (
1 , n
)
(
2 ,3
) (
2 ,4
)
-
(
2 , n - 1
) (
2 , n
)
(
3 ,4
)
…
(
3 , n - 1
) (
3 , n
)
ω ⁝ ⁝
(
n - 2 , n - 1
) (
n - 2 , n
)
(
n - 1 , n
)
可以看出 ,当一个数 i 与在它后面且比它大的数 j 每做一次邻位对换
(
i , j
)
,排列的逆序数就增加
1 个. 当
i 最后与 n 做了邻位对换
(
i , n
)
之后 ,排列的逆序数就增加 n - i 个.
n 阶排列在 n - 1 阶排列的所有邻位对换的基础之上增加了 n - 1 个邻位对换
Ξ
收稿日期 :2003 - 12 - 16
作者简介 :晏建学
(
1963～
)
,男 ,云南人 ,高级实验师 ,主要从事计算机与数学的交叉应用研究.
第 13 卷第 4 期
2004 年 10 月
云南民族大学学报
(
自然科学版
)
Journal of Yunnan Nationalities University
(
Natural Sciences Edition
)
Vol. 13 ,No. 4
Oct. 2004
资源评论
