康托展开:X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0! 其中,a为整数,并且0<=ai<i(1<=i<=n)。
康托展开可以求出 某数列的 一个全排列 是 这些数的所有全排列 里第几大的一个全排列。它也可以当一个哈希函数来用。当然这里针对的是0-9这十个数字。一般用的都是1-9.0的貌似没怎么看到过。有点孤陋寡闻了。
康托展开是一个全排列到一个自然数的双射,常用于构建哈希表时的空间压缩。
康托展开的实质是计算当前排列在所有由小到大全排列中的顺序,因此是可逆的。
康托展开的an 的值是,对第n位数(从右往左数第n位),前面n-1位数有多少个数的值是比它小的。有多少个,an的值就是多少。
贴上代码:
int cantor_unfold(int p[],int n){ int i, j, count, ans = 0; int fac[] = {1,1,2,6,24,120,720,5040,40320,362880}; for(i = 1; i <= n; i ++){ count = 0; for(j = i + 1; j <= n; j ++){ if(p[j] < p[i]) count ++; } ans += count * fac[n - i]; } return ans + 1; }
如果我们想知道 1 - n 的所有全排列里第 i 大的全排列是什么样的时候,此时我们可以用康托逆展开来推出这个全排列。
1、首先将 i = i - 1;
2、得出 它的康托展开值。
3、然后 令 y = i % (n - 1)!, x = i / (n - 1)! ;
4、x表示第n位数是前n-1位数里有x个位比它小的数,所以从第j = 1位开始看。
5、若第 j 位数 已经取过,转6,否则 将已经算得的 t 位数是小于第n位数的 t 值 再+1, 若t == x + 1,则转7,否则,转6
6、j++,转 4
7、--j,第n位的值即为,j, 若--n 为0,转8,否则,令i = y, 转3
8、输出排列,结束。
附上代码:
void Cantor_inverse_unfolding(int p[],int num,int n){ int i, j, y, t, x; int boole[MAXV] = {0}; int fac[] = {1,1,2,6,24,120,720,5040,40320,362880}; num --; for(i = n - 1; i >= 0; i--){ x = num / fac[i]; num = num % fac[i]; for(j = 0,t = 1; j <= x; t++) if(!boole[t])j++; p[n - i] = --t;//之所以--t 就是因为j要自加x+2次才会退出循环,而我们只需要知道j自加x+1次时的t值,所以--t; boole[t] = 1; } return ; }
题目推荐:
http://www.nocow.cn/index.php/Translate:USACO/msquare (BFS + cantor_unfold)