(转)一种变进制数及其应用（全排列之Hash实现）

 

我们经常使用的（9php.com）数的（9php.com）进制为“常数进制”，即始终逢p进1。例如，p进制数K可表示为
    K = a0*p^0 + a1*p^1 + a2*p^2 + ... + an*p^n （其中0 <= ai <= p-1），
它可以表示任何一个自然数。

对于这种常数进制表示法，以及各种进制之间的（9php.com）转换大家应该是很熟悉的（9php.com）了，但大家可能很少听说变进制数。这里我要介绍一种特殊的（9php.com）变进制数，它能够被用来实现全排列的（9php.com）Hash函数，并且该Hash函数能够实现完美的（9php.com）防碰撞和空间利用（不会发生碰撞，且所有空间被完全使用，不多不少）。这种全排列Hash函数也被称为全排列数化技术。下面，我们就来看看这种变进制数。

我们考查这样一种变进制数：第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进制表示相对应：
    K = a0*0！ + a1*1！ + a2*2！ + a3*3！ + ... + an*n！ （其中0 <= ai <= i）。
（后面的（9php.com）变进制数均指这种变进制数，且采用前一种表示法）

先让我们来考查一下该变进制数的（9php.com）进位是否正确。假设变进制数K的（9php.com）第i位ai为i+1，需要进位，而ai*i！=(i+1)*i！=1*(i+1)！，即正确的（9php.com）向高位进1。这说明该变进制数能够正确进位，从而是一种合法的（9php.com）计数方式。

接下来我们考查n位变进制数K的（9php.com）性质：
（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进制数的（9php.com）最大值为(n+1)！-1。
（2）当所有位ai均为0时，此时K有最小值0。
因此，n位变进制数能够表示0到(n+1)！-1的（9php.com）范围内的（9php.com）所有自然数，共(n+1)！个。

在一些状态空间搜索算法中，我们需要快速判断某个状态是否已经出现，此时常常使用Hash函数来实现。其中，有一类特殊的（9php.com）状态空间，它们是由全排列产生的（9php.com），比如N数码问题。对于n个元素的（9php.com）全排列，共产生n！个不同的（9php.com）排列或状态。下面将讨论如何使用这里的（9php.com）变进制数来实现一个针对全排列的（9php.com）Hash函数。

从数的（9php.com）角度来看，全排列和变进制数都用到了阶乘。如果我们能够用0到n！-1这n！个连续的（9php.com）变进制数来表示n个元素的（9php.com）所有排列，那么就能够把全排列完全地数化，建立起全排列和自然数之间一一对应的（9php.com）关系，也就实现了一个完美的（9php.com）Hash函数。那么，我们的（9php.com）想法能否实现呢？答案是肯定的（9php.com），下面将进行讨论。

假设我们有b0，b1，b2，b3，...，bn共n+1个不同的（9php.com）元素，并假设各元素之间有一种次序关系 b0<b1<b2<...<bn。对它们进行全排列，共产生(n+1)！种不同的（9php.com）排列。对于产生的（9php.com）任一排列 c0，c1，c2，..，cn，其中第i个元素ci（1 <= i <= n）与它前面的（9php.com）i个元素构成的（9php.com）逆序对的（9php.com）个数为di（0 <= di <= i），那么我们得到一个逆序数序列d1，d2，...，dn（0 <= di <= i）。这不就是前面的（9php.com）n位变进制数的（9php.com）各个位么？于是，我们用n位变进制数M来表示该排列：
   M = d1*1！ + d2*2！ + ... + dn*n！
因此，每个排列都可以按这种方式表示成一个n位变进制数。下面，我们来考查n位变进制数能否与n+1个元素的（9php.com）全排列建立起一一对应的（9php.com）关系。

由于n位变进制数能表示(n+1)！个不同的（9php.com）数，而n+1个元素的（9php.com）全排列刚好有(n+1)！个不同的（9php.com）排列，且每一个排列都已经能表示成一个n位变进制数。如果我们能够证明任意两个不同的（9php.com）排列产生两个不同的（9php.com）变进制数，那么我们就可以得出结论：
★ 定理1 n+1个元素的（9php.com）全排列的（9php.com）每一个排列对应着一个不同的（9php.com）n位变进制数。

对于全排列的（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构成逆序对，即有x > qi，则在排列P中pi之前也有相同元素x > pi（因为x > qi且qi > pi），即在排列P中pi之前的（9php.com）元素x也与pi构成逆序对，所以pi的（9php.com）逆序数大于等于qi的（9php.com）逆序数。又qi与pi在排列P中构成pi的（9php.com）逆序对，所以pi的（9php.com）逆序数大于qi的（9php.com）逆序数。
（2）同理，如果pi > qi，那么qi的（9php.com）逆序数大于pi的（9php.com）逆序数。
因此，由（1）和（2）知，排列P和排列Q对应的（9php.com）变进制数至少有第i位不相同，即全排列的（9php.com）任意两个不同的（9php.com）排列具有不同的（9php.com）变进制数。至此，定理1得证。

计算n个元素的（9php.com）一个排列的（9php.com）变进制数的（9php.com）算法大致如下（时间复杂度为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）数，因此一般只能用于较小的（9php.com）n。
（2）有了计算排列的（9php.com）变进制数的（9php.com）算法，我们就可以使用一个大小为n！的（9php.com）数组来保存每一个排列的（9php.com）状态，使用排列的（9php.com）变进制数作为数组下标，从而实现状态的（9php.com）快速检索。如果只是标记状态是否出现，则可以用一位来标记状态。


PS:    最近研究八数码问题发现全排列的这种Hash方式的，后来在查找一些Hash函数时发现了变进制数这个东西的，发现它真是一个好东西，ACM中也经常用到..........

posted on 2009-08-04 11:13 蜗牛也Coding 阅读(1240) 评论(1)  编辑 收藏 引用

评论

# re: (转)一种变进制数及其应用（全排列之Hash实现） 2010-01-08 10:42 treg

这不是就康托展开。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理


<2009年8月>
日一二三四五六
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜