偏序集排序（二）

對於一個偏序集 $P$，我們可以利用動態規劃的方法，找出從 $P$ 的狀態開始排序，到完整排序時，最壞情形下，至少需要幾次比較。 可惜的是，這個方法需要跑遍所有可能的 $n$ 個點的偏序集，而這個數量是隨著 $n$ 越大而呈現指數級別成長的¹。

線性延伸 Linear Extensions

有沒有更有效的方法來提早排除某些「需要太多次比較」的偏序集呢？ 其實是可以的，給定一個偏序集 $P$，對於任何一個所有資料 $x_1, x_2, \ldots, x_n$ 的全排列 $\sigma$，我們說 $\sigma$ 是 $P$ 的一個線性延伸（Linear Extension），若且唯若對於任兩筆資料 $x_i$ 與 $x_j$，一旦在 $P$ 上面 $x_i < x_j$ $\implies$ 在 $\sigma$ 之中 $x_i$ 出現在 $x_j$ 前面。 如果我們用圖論的語言來描述的話，其實滿足條件的 $\sigma$ 就會是 $P$ 所對應的有向無環圖 $G_P$ 上頭的一個拓撲排序。

我們用 $e(P)$ 來表示偏序集上面的線性延伸數量，當我們寫成 $e(G)$ 的時候，也代表著一個有向圖 $G$ 中拓撲排序的方法數。兩者定義雖然不太一樣，在這裡我們不妨就混著使用了。 舉例而言，如果 $P_{\rm{total}}$ 是一個全序集，那麼它有唯一的線性延伸，因此 $e(P_{\rm{total}}) = 1$。如果 $P_\emptyset$ 是空序集，那麼任何一個排列都會是 $P_\emptyset$ 的線性延伸，此時 $e(P_\emptyset) = n!$。

還記得資訊理論給出的複雜度下界嗎？同樣的方法在這邊也適用！

性質 23

對於一個偏序集 $P$，進行兩兩比較方式排序，至少需要 $\ceil{\log e(P)}$ 次比較。

排序效率 Efficiency

從一個 $n$ 個點的偏序集 $P$ 開始，假設我們把 $x_i$ 與 $x_j$ 拿來互相比較，比完以後會得到 $P_< := P(x_i < x_j)$、或是 $P_> := P(x_i > x_j)$ 這兩種可能。 顯然對於所有 $P$ 的線性延伸，都會恰好是 $P_<$ 或 $P_>$ 的線性延伸，於是我們有 $$\label{eq} e(P) = e(P_<) + e(P_>)\text{。} \tag{*}$$

如果 $e(P_<) \neq e(P_>)$，那麼邪惡的生測資者會設計測試資料，讓你落入線性延伸數量比較大的那種情形，然後你就會「讓剛才花費的 1 次比較，得不到 1 bit 的資訊量」。換句話說，我們想像中可能會出現「效率流失」的情形。 Knuth 的書中²寫道：黃光明教授(Frank Hwang) 與林甡(Shen Lin) 定義了排序效率（Efficiency）：假設從一個空序集經過了 $k$ 次詢問後，得到一個偏序集 $P$。那麼我們定義其排序效率 Efficiency 為 $$E(P) = \frac{n!}{2^k e(P)}$$ 這個式子可以解釋為：理論上經過 $k$ 次比較，我們應該要能將 $n!$ 種排序可能縮小至 $1/2^k$ 倍數，但事實上剩存的排列數 $e(P)$ 可能仍然比 $n!/2^k$ 來得大。我們就用這個數值來量化到底到目前為止的 $k$ 次比較有沒有效率。

從上面打星號的 $\eqref{eq}$ 來看，我們知道經過一次比較後，比較糟的那個情形，其排序效率不超過當前的排序效率： $$E(P) \ge \min\{ E(P_>), E(P_<) \}$$

這個定義可以怎麼幫助我們理解排序呢？假設我們的目標，是要在 $7$ 次比較之內，排列 $n=5$ 筆資料。此時我們可以事先估計在 $7$ 次比較之後，得到全序集當下的排序效率： $$E(P_{\rm{total}}) = 5!/2^7 = 120/128 = 15/16\text{。}$$ 這告訴我們什麼？在任何的情況下，我們不應該讓排序效率降低至 $<\frac{15}{16}$。換句話說，在選擇下一個要拿來比較的 $x_i, x_j$ 的時候，我們只需要考慮那些「得出排序結果後，效率仍保持在 $\ge 15/16$ 的那些 $(x_i, x_j)$ 配對」。

如果不存在這樣的配對，我們便證明了不存在任何基於比較的排序法，能夠在 $7$ 次之內完成排序。（事實上可以做到 $7$ 次比較，請參考前幾日的最少比較排序）

這個工具可以幫助我們排除 $n=12$ 的時候需要進行的動態規劃狀態數！ 根據 Knuth 書中的解釋，經過一連串更深入的分析──我們需要兩件事情： 一、只需要考慮所有連通的、不超過 $n=12$ 個點的圖 $G$，然後每一次比較要嘛在圖上加一條邊、要嘛把兩個圖用一條邊合併起來。二、找到一個方式估計出 $e(P)$ 的值（顯然無法有效率地直接計算它），其排除效率小於 $12!/2^{29} \approx 0.89221$ 的偏序集就可以從昨天提到的 1104891746 降到 1649 了！

(tl; dr) 最後的結論就是，在展開所有排序效率 $\ge 0.89221$ 的搜索狀態時，我們始終無法達到全序集。因此可以證得 $S(12) > 29$，由 Ford-Johnson 演算法可得知 $F(12)=30$。因此得證 $S(12)=30$。

如果給定了偏序集 $P$，雖然無法精準計算出所有的線性延伸數量 $e(P)$，我們有沒有其他方式來得出 $e(P)$ 的估計呢？

備註

Linear Extension 在紡織科學裡面會被翻譯成直線伸長唷…

延伸閱讀

• 黃光明教授：我與數學研究的第一次邂逅