跳至內容

康托展開

維基百科,自由的百科全書

康托展開是一個全排列到一個自然數雙射,常用於構建哈希表時的空間壓縮。 康托展開的實質是計算當前排列在所有由小到大全排列中的順序,因此是可逆的。

以下稱第x個全排列都是指由小到大的順序。

公式

[編輯]

其中,為整數,並且

的意義參見舉例中的解釋部分

舉例

[編輯]

例如,3 5 7 4 1 2 9 6 8 展開為 98884。因為X=2*8!+3*7!+4*6!+2*5!+0*4!+0*3!+2*2!+0*1!+0*0!=98884.

解釋:

排列的第一位是3,比3小的數有兩個,以這樣的數開始的排列有8!個,因此第一項為2*8!

排列的第二位是5,比5小的數有1、2、3、4,由於3已經出現,因此共有3個比5小的數,這樣的排列有7!個,因此第二項為3*7!

以此類推,直至0*0!

用途

[編輯]

顯然,n位(0~n-1)全排列後,其康托展開唯一且最大約為n!,因此可以由更小的空間來儲存這些排列。由公式可將X逆推出唯一的一個排列。

康托展開的逆運算

[編輯]

既然康托展開是一個雙射,那麼一定可以通過康托展開值求出原排列,即可以求出n的全排列中第x大排列。

如n=5,x=96時:

首先用96-1得到95,说明x之前有95个排列.(将此数本身减去1)
用95去除4! 得到3余23,说明有3个数比第1位小,所以第一位是4.
用23去除3! 得到3余5,说明有3个数比第2位小,所以是4,但是4已出现过,因此是5.
用5去除2!得到2余1,类似地,这一位是3.
用1去除1!得到1余0,这一位是2.
最后一位只能是1.
所以这个数是45321.

按以上方法可以得出通用的算法。

參考文獻

[編輯]
  1. Thomas H. Cormen (EDT),Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms,Third Edition. USA: The MIT Press. ISBN 978-0-262-03384-8 (英語).