亚洲欧美成人久久综合中文网,国内精品久久久久久久久电影网 ,国产免费久久精品丫丫

(轉(zhuǎn))一種變進制數(shù)及其應(yīng)用（全排列之Hash實現(xiàn)）

我們經(jīng)常使用的（9php.com）數(shù)的（9php.com）進制為“常數(shù)進制”，即始終逢p進1。例如，p進制數(shù)K可表示為
K = a0*p^0 + a1*p^1 + a2*p^2 + ... + an*p^n （其中0 <= ai <= p-1），
它可以表示任何一個自然數(shù)。

對于這種常數(shù)進制表示法，以及各種進制之間的（9php.com）轉(zhuǎn)換大家應(yīng)該是很熟悉的（9php.com）了，但大家可能很少聽說變進制數(shù)。這里我要介紹一種特殊的（9php.com）變進制數(shù)，它能夠被用來實現(xiàn)全排列的（9php.com）Hash函數(shù)，并且該Hash函數(shù)能夠?qū)崿F(xiàn)完美的（9php.com）防碰撞和空間利用（不會發(fā)生碰撞，且所有空間被完全使用，不多不少）。這種全排列Hash函數(shù)也被稱為全排列數(shù)化技術(shù)。下面，我們就來看看這種變進制數(shù)。

我們考查這樣一種變進制數(shù)：第1位逢2進1，第2位逢3進1，……，第n位逢n+1進1。它的（9php.com）表示形式為
K = a1*1！ + a2*2！ + a3*3！ + ... + an*n！（其中0 <= ai <= i），
也可以擴展為如下形式（因為按定義a0始終為0），以與p進制表示相對應(yīng)：
K = a0*0！ + a1*1！ + a2*2！ + a3*3！ + ... + an*n！（其中0 <= ai <= i）。
（后面的（9php.com）變進制數(shù)均指這種變進制數(shù)，且采用前一種表示法）

先讓我們來考查一下該變進制數(shù)的（9php.com）進位是否正確。假設(shè)變進制數(shù)K的（9php.com）第i位ai為i+1，需要進位，而ai*i！=(i+1)*i！=1*(i+1)！，即正確的（9php.com）向高位進1。這說明該變進制數(shù)能夠正確進位，從而是一種合法的（9php.com）計數(shù)方式。

接下來我們考查n位變進制數(shù)K的（9php.com）性質(zhì)：
（1）當所有位ai均為i時，此時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進制數(shù)的（9php.com）最大值為(n+1)！-1。
（2）當所有位ai均為0時，此時K有最小值0。
因此，n位變進制數(shù)能夠表示0到(n+1)！-1的（9php.com）范圍內(nèi)的（9php.com）所有自然數(shù)，共(n+1)！個。

在一些狀態(tài)空間搜索算法中，我們需要快速判斷某個狀態(tài)是否已經(jīng)出現(xiàn)，此時常常使用Hash函數(shù)來實現(xiàn)。其中，有一類特殊的（9php.com）狀態(tài)空間，它們是由全排列產(chǎn)生的（9php.com），比如N數(shù)碼問題。對于n個元素的（9php.com）全排列，共產(chǎn)生n！個不同的（9php.com）排列或狀態(tài)。下面將討論如何使用這里的（9php.com）變進制數(shù)來實現(xiàn)一個針對全排列的（9php.com）Hash函數(shù)。

從數(shù)的（9php.com）角度來看，全排列和變進制數(shù)都用到了階乘。如果我們能夠用0到n！-1這n！個連續(xù)的（9php.com）變進制數(shù)來表示n個元素的（9php.com）所有排列，那么就能夠把全排列完全地數(shù)化，建立起全排列和自然數(shù)之間一一對應(yīng)的（9php.com）關(guān)系，也就實現(xiàn)了一個完美的（9php.com）Hash函數(shù)。那么，我們的（9php.com）想法能否實現(xiàn)呢？答案是肯定的（9php.com），下面將進行討論。

假設(shè)我們有b0，b1，b2，b3，...，bn共n+1個不同的（9php.com）元素，并假設(shè)各元素之間有一種次序關(guān)系 b0<b1<b2<...<bn。對它們進行全排列，共產(chǎn)生(n+1)！種不同的（9php.com）排列。對于產(chǎn)生的（9php.com）任一排列 c0，c1，c2，..，cn，其中第i個元素ci（1 <= i <= n）與它前面的（9php.com）i個元素構(gòu)成的（9php.com）逆序?qū)Φ模?php.com）個數(shù)為di（0 <= di <= i），那么我們得到一個逆序數(shù)序列d1，d2，...，dn（0 <= di <= i）。這不就是前面的（9php.com）n位變進制數(shù)的（9php.com）各個位么？于是，我們用n位變進制數(shù)M來表示該排列：
M = d1*1！ + d2*2！ + ... + dn*n！
因此，每個排列都可以按這種方式表示成一個n位變進制數(shù)。下面，我們來考查n位變進制數(shù)能否與n+1個元素的（9php.com）全排列建立起一一對應(yīng)的（9php.com）關(guān)系。

由于n位變進制數(shù)能表示(n+1)！個不同的（9php.com）數(shù)，而n+1個元素的（9php.com）全排列剛好有(n+1)！個不同的（9php.com）排列，且每一個排列都已經(jīng)能表示成一個n位變進制數(shù)。如果我們能夠證明任意兩個不同的（9php.com）排列產(chǎn)生兩個不同的（9php.com）變進制數(shù)，那么我們就可以得出結(jié)論：
★ 定理1 n+1個元素的（9php.com）全排列的（9php.com）每一個排列對應(yīng)著一個不同的（9php.com）n位變進制數(shù)。

對于全排列的（9php.com）任意兩個不同的（9php.com）排列p0，p1，p2，...，pn（排列P）和q0，q1，q2，...，qn（排列Q），從后往前查找第一個不相同的（9php.com）元素，分別記為pi和qi（0 < i <= n）。
（1）如果qi > pi，那么，
如果在排列Q中qi之前的（9php.com）元素x與qi構(gòu)成逆序?qū)?，即有x > qi，則在排列P中pi之前也有相同元素x > pi（因為x > qi且qi > pi），即在排列P中pi之前的（9php.com）元素x也與pi構(gòu)成逆序?qū)?，所以pi的（9php.com）逆序數(shù)大于等于qi的（9php.com）逆序數(shù)。又qi與pi在排列P中構(gòu)成pi的（9php.com）逆序?qū)?，所以pi的（9php.com）逆序數(shù)大于qi的（9php.com）逆序數(shù)。
（2）同理，如果pi > qi，那么qi的（9php.com）逆序數(shù)大于pi的（9php.com）逆序數(shù)。
因此，由（1）和（2）知，排列P和排列Q對應(yīng)的（9php.com）變進制數(shù)至少有第i位不相同，即全排列的（9php.com）任意兩個不同的（9php.com）排列具有不同的（9php.com）變進制數(shù)。至此，定理1得證。

計算n個元素的（9php.com）一個排列的（9php.com）變進制數(shù)的（9php.com）算法大致如下（時間復(fù)雜度為O(n^2)）：
template <typename T>
size_t PermutationToNumber(const T permutation[]， int n)
{
// n不能太大，否則會溢出（如果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;
}

說明：
（1）由于n！是一個很大的（9php.com）數(shù)，因此一般只能用于較小的（9php.com）n。
（2）有了計算排列的（9php.com）變進制數(shù)的（9php.com）算法，我們就可以使用一個大小為n！的（9php.com）數(shù)組來保存每一個排列的（9php.com）狀態(tài)，使用排列的（9php.com）變進制數(shù)作為數(shù)組下標，從而實現(xiàn)狀態(tài)的（9php.com）快速檢索。如果只是標記狀態(tài)是否出現(xiàn)，則可以用一位來標記狀態(tài)。

PS:    最近研究八數(shù)碼問題發(fā)現(xiàn)全排列的這種Hash方式的，后來在查找一些Hash函數(shù)時發(fā)現(xiàn)了變進制數(shù)這個東西的，發(fā)現(xiàn)它真是一個好東西，ACM中也經(jīng)常用到..........

posted on 2009-08-04 11:13 蝸牛也Coding 閱讀(1196) 評論(1) 編輯收藏引用

# re: (轉(zhuǎn))一種變進制數(shù)及其應(yīng)用（全排列之Hash實現(xiàn)） 2010-01-08 10:42 treg

(轉(zhuǎn))一種變進制數(shù)及其應(yīng)用（全排列之Hash實現(xiàn)）

評論

導(dǎo)航

統(tǒng)計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理