我们经常使用的数的进制为"常数进制"，即始终逢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）。
（后面的变进制数均指这种变进制数，且采用前一种表示法）
Read full article from 变进制数与全排列的Hash函数
No comments:
Post a Comment