蓝桥杯 第十天 ：2022 国赛 第 2 题 排列距离/康托定理

实际上就是求字典序：

假设我们有 3 个数字：1, 2, 3。

• 排列组合总数: 3! = 3 * 2 * 1 = 6 种。 这 6 种排列分别是：

  1. 1 2 3
  2. 1 3 2
  3. 2 1 3
  4. 2 3 1
  5. 3 1 2
  6. 3 2 1

• 康托展开:

  • 对于排列 2 1 3，康托展开计算的结果是 2。这意味着 2 1 3 在所有 6 种排列中，按字典序排在第 3 位（因为从 0 开始计数）。
  • 对于排列 3 2 1，康托展开计算的结果是 5。这意味着 3 2 1 在所有 6 种排列中，按字典序排在第 6 位。
  • 对于排列 1 2 3, 康托展开计算的结果是0。这意味着 1 2 3 在所有6种排列中，按字典序排在第 1 位。

        private static final String A = "aejcldbhpiogfqnkr";private static final String B = "ncfjboqiealhkrpgd";public static void main(String[] args) {// 计算排列B相对于排列A的位置差long t = tak(B) - tak(A);// 如果t是负数，则取绝对值t = Math.abs(t);//这个就是顺着排的值// 取最小值，即从A到B或者从B到A的最小步数t = Math.min(t, check(17) - t);//看看是顺着排还是逆着排// 输出结果System.out.println(t);}// 计算阶乘private static long check(int n) {//17个数的全排列一共有多少个if (n == 0) return 0;long t = 1;// 计算n的阶乘for (int i = 1; i <= n; i++)t *= i;return t;}// 计算排列a在次序，能排第几个private static long tak(String a) {long ans = 0;// 对于排列a的每一个字符for (int i = 0; i < a.length(); i++) {int t = 0;// 计算在当前位置之后有多少个小于当前字符的字符for (int j = i + 1; j < a.length(); j++) {if (a.charAt(j) < a.charAt(i))t++;}// 根据康托展开公式计算当前位置的贡献ans += check(a.length() - 1 - i) * t;//t乘阶乘}return ans;}