Go语言视频零基础入门到精通

javalearner

我们经常使用的数的进制为“常数进制”，即始终逢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）。

（后面的变进制数均指这种变进制数，且采用前一种表示法）  例:十进数 变进制数 十进制
      0   =       0 =        0
      1   =       1 =       1*1!
      2   =      10 =      1*2!+0*1!
      3   =      11 =      1*2!+1*1!
      4   =      20 =      2*2!+0*1!
      5   =      21 =      2*2!+1*1!
      6   =      100 =    1*3!+0*2!+0*1!
      7   =      101 =     1*3!+0*2!+1*1!
      8   =      110 =     1*3!+1*2!+0*1!
      9   =      111 =     1*3!+1*2!+1*1!
      10  =     120 =     1*3!+2*2!+0*1!
      11  =     121 =     1*3!+2*2!+1*1!
      12  =      200 =    2*3!+0*2!+0*1!

    先让我们来考查一下该变进制数的进位是否正确。假设变进制数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
=(1+2)*2!+3*3!+...+n*n!-1
= 3!+3*3!+...+n*n!-1
..................
= (n+1)！-1
因此，n位变进制数的最大值为(n+1)！-1。  (2）当所有位ai均为0时，此时K有最小值0。
因此，n位变进制数能够表示0到(n+1)！-1的范围内的所有自然数，共(n+1)！个。
如:8位变进制数能表示0到(9!-1)内的所有自然数,有9!个.
  三、全排列的Hash函数：       在一些状态空间搜索算法中，我们需要快速判断某个状态是否已经出现，此时常常使用Hash函数来实现。
其中，有一类特殊的状态空间，它们是由全排列产生的，比如N数码问题。对于n个元素的全排列，共产生n！个不同的排列或状态。
下面将讨论如何使用这里的变进制数来实现一个针对全排列的Hash函数。       从数的角度来看，全排列和变进制数都用到了阶乘。如果我们能够用0到n！-1这n！个连续的变进制数来表示n个元素的所有排列， 那么就能够把全排列完全地数化，建立起全排列和自然数之间一一对应的关系，也就实现了一个完美的Hash函数。
那么，我们的想法能否实现呢？答案是肯定的，下面将进行讨论。     假设我们有b0，b1，b2...bn 共 n+1 个不同的元素，假设各元素之间有一种次序关系b0 < b1 < b2 ...< bn。对它们进行全排列， 共产生(n+1)！种不同的排列。对于产生的任一排列 c0，c1，c2，..，cn，其中第i个元素ci（1 <= i <= n）与
它前面的i个元素构成的逆序对的个数为di（0 <= di <= i），那么我们得到一个逆序数序列d1，d2，...，dn（0 <= di <= i）。
这不就是前面的n位变进制数的各个位么？于是，我们用n位变进制数M来表示该排列：
          M = d1*1！ + d2*2！ + ... + dn*n！
因此，每个排列都可以按这种方式表示成一个n位变进制数。下面，我们来考查n位变进制数能否与n+1个元素的全排列建立起一一对应的关系。     由于n位变进制数能表示(n+1)！个不同的数，而n+1个元素的全排列刚好有(n+1)！个不同的排列，
且每一个排列都已经能表示成一个n位变进制数。如果我们能够证明任意两个不同的排列产生两个不同的变进制数，那么我们就可以得出结论：  定理:
    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位不相同，即全排列的任意两个不同的排列具有不同的变进制数。
至此，定理得证。
  四、计算k个元素的一个全排列对应的变进制数的算法(hash函数)

1. public class Test{
   
2.   //1!=1;2!=2;3!=6;4!=24;5!=120;6!=720...
   
3.   static int fac[] = {1,2,6,24,120,720,5040,40320};
   
4.   static int hash(int num,int k){// k个不同元素的全排列的hash函数。s是K个元素的一个排列
   
5.     int  n[]=new int[k];
   
6.     for(int i = k-1; i >=0; i--){
   
7.         n[i] = num % 10;
   
8.         num /= 10;
   
9.     }
   
10.    
    
11.     int key = 0;
    
12.     int c;
    
13.     for(int i = 1; i < k; i++){
    
14.          c=0;
    
15.      for(int j = 0; j < i; j++)
    
16.          if(n[j] > n[i]) c++;
    
17.      key += c * fac[i-1];
    
18.     }
    
19.     return key;
    
20. }
    
21. static int hash(String s,int k){// k个不同元素的全排列的hash函数。
    
22.     int  n[]=new int[k];
    
23.     for(int i = k-1; i >=0; i--){
    
24.         int num=s.charAt(i)-48;
    
25.         n[i] = num % 10;
    
26.         num /= 10;
    
27.     }
    
28.    
    
29.     int key = 0;
    
30.     int c;
    
31.     for(int i = 1; i < k; i++){
    
32.          c=0;
    
33.      for(int j = 0; j < i; j++)
    
34.          if(n[j] > n[i]) c++;
    
35.      key += c * fac[i-1];
    
36.     }
    
37.     return key;
    
38. }
    
39.   
    
40.   public static void main(String[] args){
    
41.     int a[]={123,132,213,231,312,321};
    
42.     for(int i=0;i< a.length;i++)
    
43.       System.out.println(hash(a[i],3));
    
44.       System.out.println(hash("012345678",9));
    
45.        System.out.println(hash("876543210",9));
    
46.          System.out.println(hash(876543210,9));
    
47. }
    
48.    
    
49.    }
    

复制代码

运行：
D:java>java   Test
0
2
1
4
3
5
0
362879
362879


   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/12/5/001026484.zip