这题的主要问题是hash值,题中是123456789来填格子,共9个数,对九个数进行排序,如果用数组存储9个数排列时产生的状态,需要开很大的数组,这也是本题的难点。

先介绍下一个整数表示法 (n!)=(n-1+1)(n-1)!=(n-1)(n-1)!+(n-1)!;

同理(n-1)!=(n-2)(n-2)!+(n-2)!;

所以n!=(n-1)(n-1)!+(n-2)(n-2)!+(n-3)(n-3)!+…..+2*2!+2!;

因为2!=1+1;

所以n!-=(n-1)(n-1)!+(n-2)(n-2)!+(n-3)(n-3)!+…..+d*2!+1;

所以n!-1=(n-1)(n-1)!+(n-2)(n-2)!+(n-3)(n-3)!+…..+2*2!+1*1!;

所以从0到n!-1的任何整数m可唯一的表示为

m=a(n-1)!+b(n-2)!+c(n-3)!+…..+h*2!+j*1;

所以一个整数m对应一个序列(a,b,c,…..h,j);

设序列(a,b,c….h,j)对应一个排列p=(p1,p2,p3,p4…pn);

其中a,b,c…h,j可以看成是排列p中数i+1所在位置后面i+1小的数的个数,也就是排列p中从数i+1开始后向右统计小于或等于i的个数,以排列4213为例,4后面比他小的的数的个数即a3为3;3后面比他小的数的个数即a2等于0;2后面比他小的数的个数a1为1;排列中比1小的数是没有的,故得p=(4213)<==>(a3a2a1)=(301);

而(301)对应一个整数(看上面);

所以123456789共9个数的全排列,可以产生一个排序(a1,a2,a3,a5,a6,a7,a8),而通过这个排序可以产生一个数

m=a8*(8)!+a7*(7)!+…+a1*(1)!;

发表评论

电子邮件地址不会被公开。

Post Navigation