Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1075227
  • 博文数量: 77
  • 博客积分: 11498
  • 博客等级: 上将
  • 技术积分: 1840
  • 用 户 组: 普通用户
  • 注册时间: 2006-05-04 11:10
文章分类

全部博文(77)

文章存档

2011年(1)

2010年(16)

2009年(5)

2008年(55)

分类: C/C++

2008-10-07 23:53:44


    一种变进制数及其应用(全排列之Hash实现)
    作者:tyc611.cublog.cn,2008-10-08
我们经常使用的数的进制为“常数进制”,即始终逢p进1。例如,p进制数K可表示为
    K = a0*p^0 + a1*p^1 + a2*p^2 + ... + an*p^n (其中0 <= ai <= p-1),
它可以表示任何一个自然数。

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

我们考查这样一种变进制数:第1位逢2进1,第2位逢3进1,……,第n位逢n+1进1。它的表示形式为
    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)。
(后面的变进制数均指这种变进制数,且采用前一种表示法)

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

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

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

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

假设我们有b0,b1,b2,b3,...,bn共n+1个不同的元素,并假设各元素之间有一种次序关系b0   M = d1*1! + d2*2! + ... + dn*n!
因此,每个排列都可以按这种方式表示成一个n位变进制数。下面,我们来考查n位变进制数能否与n+1个元素的全排列建立起一一对应的关系。

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

对于全排列的任意两个不同的排列p0,p1,p2,...,pn(排列P)和q0,q1,q2,...,qn(排列Q),从后往前查找第一个不相同的元素,分别记为pi和qi(0 < i <= n)。
(1)如果qi > pi,那么,
如果在排列Q中qi之前的元素x与qi构成逆序对,即有x > qi,则在排列P中pi之前也有相同元素x > pi(因为x > qi且qi > pi),即在排列P中pi之前的元素x也与pi构成逆序对,所以pi的逆序数大于等于qi的逆序数。又qi与pi在排列P中构成pi的逆序对,所以pi的逆序数大于qi的逆序数。
(2)同理,如果pi > qi,那么qi的逆序数大于pi的逆序数。
因此,由(1)和(2)知,排列P和排列Q对应的变进制数至少有第i位不相同,即全排列的任意两个不同的排列具有不同的变进制数。至此,定理1得证。

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

最后,附上一段完整的代码来演示使用变进制数实现全排列的数化(或者Hash,随便怎么称乎了)。

文件:src.zip
大小:4KB
下载:下载

2008.10.9 补充:
在“十进制数 <--> 变进制数 <--> 排列”的转换中,
(1)从十进制数到变进制数的转换方法与p进制数之间的转换类似,但区别是被除数和模数是依次是2,3,4,...n,而不是固定的p
(2)从变进制数到排列的转换算法如下:
使用一个有序的(升序)元素集合作为初始待排子集,然后按照如下过程处理:
从变进制数的高位向低位扫描,对于变进制数的每一位ai,
从当前待排子集中选出第ai+1大元素E,并把它与当前待排子集中它后面的子序列进行交换,然后从当前待排子集中去掉元素E
重复以上过程,直到所有变进制数的位扫描完毕,此时当前待排子集将刚好剩下一个元素,得到与变进制数对应的排列

“十进制数 <--> 变进制数 <--> 排列”之间的转换代码如下:
#include
#include
#include
#include
#include

using namespace std;

// 把十进制数转换为变进制数,并返回变进制数的位数
// 变进制数varNumber[0]对应着变进制数的最低位
int DecimalToVariableRadix(size_t decimalNumber, vector &varNumber)
{
    varNumber.clear();

    int carry = 2;
    while (decimalNumber > 0) {
        varNumber.push_back(decimalNumber % carry);
        decimalNumber /= carry;
        ++carry;
    }

    if (varNumber.empty())
        varNumber.push_back(0);

    return varNumber.size();
}

// 把十进制数转换为指定位数的变进制数(高位填充0),并返回变进制数的实际有效位数
// 如果产生的变进制数的位数比指定的位数要多,则指定位数不起作用
// 变进制数varNumber[0]对应着变进制数的最低位
int DecimalToVariableRadix(size_t decimalNumber, vector &varNumber, int num)
{
    varNumber.clear();

    int carry = 2;
    while (decimalNumber > 0) {
        varNumber.push_back(decimalNumber % carry);
        decimalNumber /= carry;
        ++carry;
    }

    int size = varNumber.size();
    if (size < num)
        varNumber.insert(varNumber.end(), num - size, 0);

    return size;
}

// 把变进制数转换为十进制数
// 变进制数varNumber[0]对应着变进制数的最低位
size_t VariableRadixToDecimal(const int varNumber[], int num)
{
    size_t factor = 1;
    size_t result = 0;
   
    for (int i = 0; i < num; ++i) {
        result += varNumber[i] * factor;
        factor *= i + 2;
    }

    return result;
}

// 把排列转换为变进制数,变进制数的高位可能会出现多个0
// 变进制数varNumber[0]对应着变进制数的最低位
template
void PermutationToVariableRadix(const ElemType permutation[], int num, vector &varNumber)
{
    for (int i = 1; i < num; ++i) {
        int count = 0;
        for (int k = 0; k < i; ++k) {
            if (permutation[k] > permutation[i])
                ++count;
        }
        varNumber.push_back(count);
    }
}

// 把变进制数转换为排列,要求传入的排列元素集合是有序的(升序)
// 并且要求变进制数的位数(包括高位的0)刚好比排列元素少一
// 变进制数varNumber[0]对应着变进制数的最低位
template
void VariableRadixToPermutation(const int varNumber[], int num, ElemType perm[])
{
    for (int k = num - 1; k >= 0; --k) {
        // 交换当前待排子集中第(varNumber[k] + 1)大元素和它后面的子序列
        int m = k + 1;             // 当前待排子集中最后一个元素下标
        int j = m - varNumber[k];  // 当前待排子集中第(varNumber[k] + 1)大元素
#if 0
        // 实现std::rotate的功能
        ElemType tmp = perm[j];
        for (; j < m; ++j)
            perm[j] = perm[j + 1];
        perm[m] = tmp;
#else
        rotate(perm + j, perm + j + 1, perm + m + 1);
#endif
    }
}

//////////////////////////////////////////////////////////////////////////////////////
class AssureException: public std::exception
{
};

#define Assure(os, x) (void)((!!(x)) || (ShowFailedMessage(os, #x, __FILE__, __LINE__), 0))

inline void ShowFailedMessage(std::ostream &os, const char* expr, const char *file, size_t line)
{
    os << "Failed: " << expr << ", file \"" << file << "\", line " << line << '\n';
    throw AssureException();
}


void ShowUsage1()
{
    try {
        size_t num = 235;
        vector varNumber;

        DecimalToVariableRadix(num, varNumber);
        cout << "Decimal number: " << num;
        cout << "\nConverted to variable radix number (low -> high): ";
        copy(varNumber.begin(), varNumber.end(), ostream_iterator(cout, " "));

        size_t newNum = VariableRadixToDecimal(&varNumber[0], varNumber.size());
        cout << "\nConverted back to decimal number: " << newNum << '\n';

        Assure(cout, num == newNum);
        cout << endl;
    }
    catch (AssureException) {
    }
}

void ShowUsage2()
{
    try {
        char perm[] = {'d', 'e', 'a', 'b', 'f', 'c', 'g'};
        const int NUM = sizeof(perm) / sizeof(perm[0]);
        vector varNumber;

        PermutationToVariableRadix(perm, NUM, varNumber);
        cout << "Permutation: ";
        copy(perm, perm + NUM, ostream_iterator(cout));
        cout << "\nConverted to variable radix number (low -> high): ";
        copy(varNumber.begin(), varNumber.end(), ostream_iterator(cout, " "));

        char newPerm[NUM] = {'a', 'b', 'c', 'd', 'e', 'f', 'g'};
        VariableRadixToPermutation(&varNumber[0], varNumber.size(), newPerm);
        cout << "\nConverted back to permutation: ";
        copy(newPerm, newPerm + NUM, ostream_iterator(cout));
        cout << '\n';

        Assure(cout, equal(perm, perm + NUM, newPerm));
        cout << endl;
    }
    catch (AssureException) {
    }
}

void Test()
{
    try {
        cout << "testing \"permutation -> variable radix -> decimal -> "
            "variable radix -> permutation\"...";

        const int NUM = 9;
        char perm[NUM] = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};

        do {
            // permutation will be  converted to variable radix number
            vector varNumber;
            PermutationToVariableRadix(perm, NUM, varNumber);

            // variable radix number will be converted to decimal number
            size_t decimalNumber = VariableRadixToDecimal(&varNumber[0], varNumber.size());

            // decimal number will be converted back to variable radix number
            vector newVarNumber;
            DecimalToVariableRadix(decimalNumber, newVarNumber, NUM - 1);

            // variable radix number will be converted back to permutation
            char newPerm[NUM] = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};
            VariableRadixToPermutation(&newVarNumber[0], newVarNumber.size(), newPerm);

            Assure(cout, equal(varNumber.begin(), varNumber.end(), newVarNumber.begin()));
            Assure(cout, equal(perm, perm + NUM, newPerm));
        } while (next_permutation(perm, perm + NUM));

        cout << "done. Ok!" << endl;
    }
    catch (AssureException) {
    }
}

int main()
{
    ShowUsage1();
    ShowUsage2();
    Test();
}

阅读(1244) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~