Ark's Blog

参加記や備忘録などを書いていきます

ようこそ

転倒数と測度の話

転倒数について調べてたらwikipediaに気になる記述があった。

列の転倒数 (inversion number) は、その整列性の測度として広く用いられる[3][2]。(wikipedia)

いったいどんな可測空間上で定義された測度なんだ?と気になって調べた。

この「測度」は正式には事前整列性測度(measure of presortedness)というらしく、全順序集合の列がどの程度整列しているかを示す"指標"のことだった。ソートアルゴリズムの評価などで使うことがあるらしい(?)。測度論における「測度」とは別の概念だった。(「対象の大きさ・程度を表す」という意味では似た概念)

ついでに定義を以下にまとめる。

定義とか

Def.1 記法

$\mathbb{N} := \text{「非負の整数全体の集合」}$ #0は自然数

$\mathbb{N}^{<\mathbb{N}} := \text{「非負整数による有限列全体の集合」}$

$^\forall X=(x_1, x_2, \ldots, x_n), Y=(y_1, y_2, \ldots, y_m) \in \mathbb{N}^{<\mathbb{N}}$について

  • $X \leq Y$ $\,:\Leftrightarrow\,$ $^\forall i\in \{1, \ldots, n\}, ^\forall j\in \{1, \ldots, m\}, x_i \leq y_j$
  • $XY := (x_1, x_2, \ldots, x_n, y_1, y_2, \ldots, y_m)$
  • $|X| := $「$X$の要素‌数」

と定義する。

E.g.2

  • $(0, 1, 2), (2, 1, 0) \in \mathbb{N}^{<\mathbb{N}}$
  • $(1, -2) \notin \mathbb{N}^{<\mathbb{N}}$
  • $(1, 3) \leq (5, 8)$
  • $(3, 3, 4)(1, 2) = (3, 3, 4, 1, 2)$

Def.3 事前整列性測度

$m: \mathbb{N}^{<\mathbb{N}} \rightarrow \mathbb{N}$が次の(1)~(5)を満たすとき、m事前整列性測度(measure of presortedness)、または単に整列性測度という。

  1. $^\forall X \in \mathbb{N}^{<\mathbb{N}},$ $X\text{が昇順である} \Rightarrow m(X)=0$
  2. $^\forall X=(x_1, x_2, \ldots, x_n), Y=(y_1, y_2, \ldots, y_n) \in \mathbb{N}^{<\mathbb{N}},$ $(^\forall i, j \in \{1, 2, \ldots, n\},\, x_i \leq x_j \Leftrightarrow y_i \leq y_j) \Rightarrow m(X) = m(Y)$
  3. $^\forall X, Y \in \mathbb{N}^{<\mathbb{N}},$ $Y\text{が}X\text{の部分列(subsequence)である} \Rightarrow m(Y) \leq m(X)$
  4. $^\forall X, Y \in \mathbb{N}^{<\mathbb{N}},$ $X \leq Y \Rightarrow m(XY) \leq m(X) + m(Y)$
  5. $^\forall x \in \mathbb{N}, m( (x)X )\leq |X| + m(X)$

Def.4 転倒数 $\rm{Inv}$

$\rm{Inv}: \mathbb{N}^{<\mathbb{N}} \rightarrow \mathbb{N}$が

$^\forall X=(x_1, x_2, \ldots, x_n) \in \mathbb{N}^{<\mathbb{N}}$ $\rm{Inv}(X) := |\{ (i, j) \mid 1\leq i < j \leq n \land x_i > x_j \}|$

をみたすとき、$\rm{Inv}$を転倒数(inversion number)という。

Thm.5

転倒数$\rm{Inv}$は事前整列性測度である。

proof: たぶん成り立ってると思うけどめんどそうなので省略。

雑記

  • 転倒数以外にも整列性測度となるような関数は色々考えられてきたみたい。興味がある人は参考文献などを見てください。

参考文献

  • Mannila, Heikki (1984). “Measures of presortedness and optimal sorting algorithms”. Lecture Notes in Computer Science 172: 324–336. doi:10.1007/3-540-13345-3_29.
  • Estivill-Castro, Vladimir; Wood, Derick (1989). “A new measure of presortedness”. Information and Computation 83 (1): 111–119.