每日算法 — 使用java实现康托展开：排列序号双向映射与全排列枚举

算法概述

康托展开（Cantor Expansion）是一种将全排列映射为非负整数的经典算法，在组合数学中具有重要地位。对于 n 个不同元素的全排列，康托展开可以将任意排列唯一映射到 0 到 n!−1 的整数（称为排列的排名），同时也支持逆运算——给定排名还原出对应的排列。

该算法广泛应用于密码学、博弈状态压缩、排列索引生成、竞赛编程中的状态空间优化等场景。

核心原理

1. 排列排名：对于排列 p[0..n−1]，其康托值为
   rank = Σ (count[i] × (n−1−i)!)
   其中 count[i] 表示在 p[i] 右侧且小于 p[i] 的元素个数。

2. 逆康托展开：给定 rank 和 n，从最高位到最低位依次确定每个位置的元素：

3. 将 rank 除以 (n−1−i)! 得到 count[i]
4. 在未使用的元素中选择第 count[i] 小的元素

5. rank 更新为 rank mod (n−1−i)!

6. 阶乘预处理：预先计算 0! 到 n! 的值，避免重复计算。

Java 实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 康托展开算法实现
 * 支持排列到排名的映射（康托展开）与排名到排列的逆映射
 */
public class CantorExpansion {
    // 最大支持到 20!（超过 long 范围）
    private static final int MAX_N = 20;
    // 阶乘表
    private final long[] factorial;

    public CantorExpansion() {
        factorial = new long[MAX_N + 1];
        factorial[0] = 1;
        for (int i = 1; i <= MAX_N; i++) {
            factorial[i] = factorial[i - 1] * i;
        }
    }

    /**
     * 康托展开：将排列映射为排名（0 开始）
     * @param permutation 排列数组，元素为 0~n-1 的不重复整数
     * @return 排列的排名
     */
    public long encode(int[] permutation) {
        int n = permutation.length;
        if (n > MAX_N) {
            throw new IllegalArgumentException("排列长度超过最大支持值 " + MAX_N);
        }
        long rank = 0;
        // 使用树状数组优化计数，时间复杂度 O(n log n)
        FenwickTree ft = new FenwickTree(n);
        for (int i = 0; i < n; i++) {
            // 统计右侧未出现且小于当前元素的个数
            int count = ft.query(permutation[i] - 1);
            rank += (long) count * factorial[n - 1 - i];
            ft.update(permutation[i], 1);
        }
        return rank;
    }

    /**
     * 逆康托展开：将排名还原为排列
     * @param rank 排列排名（0 开始）
     * @param n 排列长度
     * @return 对应的排列
     */
    public int[] decode(long rank, int n) {
        if (n > MAX_N) {
            throw new IllegalArgumentException("排列长度超过最大支持值 " + MAX_N);
        }
        if (rank < 0 || rank >= factorial[n]) {
            throw new IllegalArgumentException("排名超出有效范围 [0, " + factorial[n] + ")");
        }

        int[] result = new int[n];
        // 可用元素列表
        List<Integer> available = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            available.add(i);
        }

        for (int i = 0; i < n; i++) {
            long fac = factorial[n - 1 - i];
            int index = (int) (rank / fac);
            rank %= fac;
            result[i] = available.remove(index);
        }
        return result;
    }

    /**
     * 暴力法计算康托展开（O(n^2)，用于验证）
     */
    public long encodeBruteForce(int[] permutation) {
        int n = permutation.length;
        long rank = 0;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = i + 1; j < n; j++) {
                if (permutation[j] < permutation[i]) count++;
            }
            rank += (long) count * factorial[n - 1 - i];
        }
        return rank;
    }

    /**
     * 获取 n 的阶乘值
     */
    public long getFactorial(int n) {
        return factorial[n];
    }

    /**
     * 树状数组（Fenwick Tree），用于高效统计小于某值的元素个数
     */
    private static class FenwickTree {
        private final int[] tree;
        private final int n;

        FenwickTree(int n) {
            this.n = n;
            this.tree = new int[n + 2];
        }

        // 在位置 idx 增加 delta
        void update(int idx, int delta) {
            idx++; // 转为 1-based
            while (idx <= n + 1) {
                tree[idx] += delta;
                idx += idx & -idx;
            }
        }

        // 查询 [0, idx] 的前缀和
        int query(int idx) {
            if (idx < 0) return 0;
            idx++;
            int sum = 0;
            while (idx > 0) {
                sum += tree[idx];
                idx -= idx & -idx;
            }
            return sum;
        }
    }

    @Override
    public String toString() {
        return "CantorExpansion(maxN=" + MAX_N + ")";
    }

    // ==================== 测试入口 ====================
    public static void main(String[] args) {
        CantorExpansion ce = new CantorExpansion();

        // 测试 1：基本编码解码
        int[] perm1 = {2, 0, 3, 1};
        long rank1 = ce.encode(perm1);
        long rank1bf = ce.encodeBruteForce(perm1);
        int[] decoded1 = ce.decode(rank1, perm1.length);

        System.out.println("原始排列: " + Arrays.toString(perm1));
        System.out.println("康托展开排名: " + rank1);
        System.out.println("暴力法验证: " + rank1bf);
        System.out.println("逆展开结果: " + Arrays.toString(decoded1));
        System.out.println("编解码一致性: " + Arrays.equals(perm1, decoded1));

        // 测试 2：枚举所有排列并验证
        int n = 5;
        System.out.println("\n枚举 " + n + " 个元素的所有排列（共 " + ce.getFactorial(n) + " 个）:");
        boolean allPass = true;
        for (long r = 0; r < ce.getFactorial(n); r++) {
            int[] perm = ce.decode(r, n);
            long back = ce.encode(perm);
            if (back != r) {
                System.out.println("不一致! rank=" + r + ", back=" + back +
                                   ", perm=" + Arrays.toString(perm));
                allPass = false;
                break;
            }
        }
        System.out.println("全部 " + ce.getFactorial(n) + " 个排列验证: " + (allPass ? "通过" : "失败"));

        // 测试 3：较大规模性能测试
        int largeN = 10;
        int largePermCount = 100000;
        long start = System.currentTimeMillis();
        for (int i = 0; i < largePermCount; i++) {
            int[] perm = ce.decode(i, largeN);
            ce.encode(perm);
        }
        long elapsed = System.currentTimeMillis() - start;
        System.out.println("\n" + largePermCount + " 次 " + largeN + " 长度编解码耗时: " + elapsed + "ms");
    }
}

复杂度分析

对于 n ≤ 20 的场景，康托展开可以完美将排列压缩为单个整数，极大优化状态存储与传输。

适用场景

• 全排列字典序索引与快速定位
• 博弈树状态压缩（如八数码、魔方状态）
• 密码学中的排列密码生成
• 竞赛编程中的排列类动态规划状态压缩
• 音乐/图像生成中的排列组合索引