我們經(jīng)常使用的數(shù)的進(jìn)制為“常數(shù)進(jìn)制”，即始終逢p進(jìn)1。例如，p進(jìn)制數(shù)K可表示為
K = a0*p^0 + a1*p^1 + a2*p^2 + ... + an*p^n （其中0 <= ai <= p-1），
它可以表示任何一個(gè)自然數(shù)。
對(duì)于這種常數(shù)進(jìn)制表示法，以及各種進(jìn)制之間的轉(zhuǎn)換大家應(yīng)該是很熟悉的了，但大家可能很少聽(tīng)說(shuō)變進(jìn)制數(shù)。這里我要介紹一種特殊的變進(jìn)制數(shù)，它能夠被用來(lái)實(shí)現(xiàn)全排列的Hash函數(shù)，并且該Hash函數(shù)能夠?qū)崿F(xiàn)完美的防碰撞和空間利用（不會(huì)發(fā)生碰撞，且所有空間被完全使用，不多不少）。這種全排列Hash函數(shù)也被稱為全排列數(shù)化技術(shù)。下面，我們就來(lái)看看這種變進(jìn)制數(shù)。
我們考查這樣一種變進(jìn)制數(shù)：第1位逢2進(jìn)1，第2位逢3進(jìn)1，……，第n位逢n+1進(jìn)1。它的表示形式為
K = a1*1! + a2*2! + a3*3! + ... + an*n! （其中0 <= ai <= i），
也可以擴(kuò)展為如下形式（因?yàn)榘炊xa0始終為0），以與p進(jìn)制表示相對(duì)應(yīng)：
K = a0*0! + a1*1! + a2*2! + a3*3! + ... + an*n! （其中0 <= ai <= i）。
（后面的變進(jìn)制數(shù)均指這種變進(jìn)制數(shù)，且采用前一種表示法）
先讓我們來(lái)考查一下該變進(jìn)制數(shù)的進(jìn)位是否正確。假設(shè)變進(jìn)制數(shù)K的第i位ai為i+1，需要進(jìn)位，而ai*i!=(i+1)*i!=1*(i+1)!，即正確的向高位進(jìn)1。這說(shuō)明該變進(jìn)制數(shù)能夠正確進(jìn)位，從而是一種合法的計(jì)數(shù)方式。
接下來(lái)我們考查n位變進(jìn)制數(shù)K的性質(zhì)：
（1）當(dāng)所有位ai均為i時(shí)，此時(shí)K有最大值
MAX[K] = 1*1! + 2*2! + 3*3! + ... + n*n!
= 1! + 1*1! + 2*2! + 3*3! + ... + n*n! - 1
= (1+1)*1! + 2*2! + 3*3! + ... + n*n! - 1
= 2! + 2*2! + 3*3! + ... + n*n! - 1
= ...
= (n+1)!-1
因此，n位K進(jìn)制數(shù)的最大值為(n+1)!-1。
（2）當(dāng)所有位ai均為0時(shí)，此時(shí)K有最小值0。
因此，n位變進(jìn)制數(shù)能夠表示0到(n+1)!-1的范圍內(nèi)的所有自然數(shù)，共(n+1)!個(gè)。
在一些狀態(tài)空間搜索算法中，我們需要快速判斷某個(gè)狀態(tài)是否已經(jīng)出現(xiàn)，此時(shí)常常使用Hash函數(shù)來(lái)實(shí)現(xiàn)。其中，有一類特殊的狀態(tài)空間，它們是由全排列產(chǎn)生的，比如N數(shù)碼問(wèn)題。對(duì)于n個(gè)元素的全排列，共產(chǎn)生n!個(gè)不同的排列或狀態(tài)。下面將討論如何使用這里的變進(jìn)制數(shù)來(lái)實(shí)現(xiàn)一個(gè)針對(duì)全排列的Hash函數(shù)。
從數(shù)的角度來(lái)看，全排列和變進(jìn)制數(shù)都用到了階乘。如果我們能夠用0到n!-1這n!個(gè)連續(xù)的變進(jìn)制數(shù)來(lái)表示n個(gè)元素的所有排列，那么就能夠把全排列完全地?cái)?shù)化，建立起全排列和自然數(shù)之間一一對(duì)應(yīng)的關(guān)系，也就實(shí)現(xiàn)了一個(gè)完美的Hash函數(shù)。那么，我們的想法能否實(shí)現(xiàn)呢？答案是肯定的，下面將進(jìn)行討論。
假設(shè)我們有b0,b1,b2,b3,...,bn共n+1個(gè)不同的元素，并假設(shè)各元素之間有一種次序關(guān)系 b0<b1<b2<...<bn。對(duì)它們進(jìn)行全排列，共產(chǎn)生(n+1)!種不同的排列。對(duì)于產(chǎn)生的任一排列 c0,c1,c2,..,cn，其中第i個(gè)元素ci（1 <= i <= n）與它前面的i個(gè)元素構(gòu)成的逆序?qū)Φ膫€(gè)數(shù)為di（0 <= di <= i），那么我們得到一個(gè)逆序數(shù)序列d1,d2,...,dn（0 <= di <= i）。這不就是前面的n位變進(jìn)制數(shù)的各個(gè)位么？于是，我們用n位變進(jìn)制數(shù)M來(lái)表示該排列：
M = d1*1! + d2*2! + ... + dn*n!
因此，每個(gè)排列都可以按這種方式表示成一個(gè)n位變進(jìn)制數(shù)。下面，我們來(lái)考查n位變進(jìn)制數(shù)能否與n+1個(gè)元素的全排列建立起一一對(duì)應(yīng)的關(guān)系。
由于n位變進(jìn)制數(shù)能表示(n+1)!個(gè)不同的數(shù)，而n+1個(gè)元素的全排列剛好有(n+1)!個(gè)不同的排列，且每一個(gè)排列都已經(jīng)能表示成一個(gè)n位變進(jìn)制數(shù)。如果我們能夠證明任意兩個(gè)不同的排列產(chǎn)生兩個(gè)不同的變進(jìn)制數(shù)，那么我們就可以得出結(jié)論：
★ 定理1 n+1個(gè)元素的全排列的每一個(gè)排列對(duì)應(yīng)著一個(gè)不同的n位變進(jìn)制數(shù)。
對(duì)于全排列的任意兩個(gè)不同的排列p0,p1,p2,...,pn（排列P）和q0,q1,q2,...,qn（排列Q），從后往前查找第一個(gè)不相同的元素，分別記為pi和qi（0 < i <= n）。
（1）如果qi > pi，那么,
如果在排列Q中qi之前的元素x與qi構(gòu)成逆序?qū)Γ从衳 > qi，則在排列P中pi之前也有相同元素x > pi（因?yàn)閤 > qi且qi > pi），即在排列P中pi之前的元素x也與pi構(gòu)成逆序?qū)Γ詐i的逆序數(shù)大于等于qi的逆序數(shù)。又qi與pi在排列P中構(gòu)成pi的逆序?qū)Γ詐i的逆序數(shù)大于qi的逆序數(shù)。
（2）同理，如果pi > qi，那么qi的逆序數(shù)大于pi的逆序數(shù)。
因此，由（1）和（2）知，排列P和排列Q對(duì)應(yīng)的變進(jìn)制數(shù)至少有第i位不相同，即全排列的任意兩個(gè)不同的排列具有不同的變進(jìn)制數(shù)。至此，定理1得證。
計(jì)算n個(gè)元素的一個(gè)排列的變進(jìn)制數(shù)的算法大致如下（時(shí)間復(fù)雜度為O(n^2)）：
template <typename T>
size_t PermutationToNumber(const T permutation[], int n)
{
// n不能太大，否則會(huì)溢出（如果size_t為32位，則n <= 12）
size_t result = 0;
for (int j = 1; j < n; ++j) {
int count = 0;
for (int k = 0; k < j; ++k) {
if (permutation[k] > permutation[j])
++count;
}
// factorials[j]保存著j!
result += count * factorials[j];
}
return result;
}
說(shuō)明：
（1）由于n!是一個(gè)很大的數(shù)，因此一般只能用于較小的n。
（2）有了計(jì)算排列的變進(jìn)制數(shù)的算法，我們就可以使用一個(gè)大小為n!的數(shù)組來(lái)保存每一個(gè)排列的狀態(tài)，使用排列的變進(jìn)制數(shù)作為數(shù)組下標(biāo)，從而實(shí)現(xiàn)狀態(tài)的快速檢索。如果只是標(biāo)記狀態(tài)是否出現(xiàn)，則可以用一位來(lái)標(biāo)記狀態(tài)。