应用康托展开求解指定串在全排序中的顺序及通过顺序求解指定串

康托展开

康托展开是一个全排列到一个自然数的双射&＃xff0c;常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序&＃xff0c;因此是可逆的。


求解指定串在全排序中的顺序

比如串 “cdba”
排列c时&＃xff0c;未出现的字符包括 a b d&＃xff0c; c在其中排第2位(从0开始计算)&＃xff1a; 2 * 3!
排列d时&＃xff0c;未出现的字符包括 a b&＃xff0c;d在其中排第2位&＃xff1a;2 * 2&＃xff01;
排列b时&＃xff0c;未出现的字符包括a, b在其中排第1位&＃xff1a; 1 * 1!
排列a时&＃xff0c;全都已经出现&＃xff0c;a排在第0位: 0 * 0!
因此 2 * 6 &＃43; 2 * 2 &＃43; 1 &＃61; 17位

通过顺序求解指定串

比如 求解第17位的串
17 / 3! &＃61; 2 余 5&＃xff0c; 说明比首位小的有2个&＃xff0c;所以首位为c
5 / 2! &＃61; 2 余 1, 说明比该位小的有2个&＃xff0c;&＃xff08;c已经用了&＃xff09;所以第二位为d
1 / 1! &＃61; 1 余 0, 说明比该位小的有1个&＃xff0c;所以第三位为b
剩下最后一个用排除法可以得到是a
因此得到的顺序为 cdba