如何交换整型数组索引与值实现置换逆映射

本文详细讲解了如何将一个表示置换（permutation）的整型数组转换为其逆置换（inverse permutation），即把原数组中“值 → 索引”的映射关系，转化为“索引 → 值”的逆映射。该操作在密码学轮转器（如 Enigma 仿真）的编码/解码对称步骤中极为常见。

在密码学模拟，尤其是 Enigma 机器转子建模的过程中，经常需要对置换数组执行逆置换操作。简单来说，给定一个数组 arr，它表示“输入位置 i 映射到输出位置 j”（即 arr[i] = j），那么逆置换 inv 必须满足 inv[j] = i，从而将输出位置反向映射回输入位置。其核心思想就是交换数组的索引与值的角色。

实现过程并不复杂，但有一个关键点必须牢记：必须使用独立的目标数组来进行计算，绝对不能在原地修改，否则数据会被污染，导致逻辑完全混乱。下面给出一个标准实现示例：

int[] arr = {4, 0, 3, 1, 2}; // 原置换：索引→值
int[] inv = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
    inv[arr[i]] = i; // 将“值 arr[i]”作为新索引，“原索引 i”作为新值
}
// 输出：[1, 3, 4, 2, 0]
System.out.println(Arrays.toString(inv));

逐步拆解逻辑后，就会非常清晰：

• arr[0] == 4 → 位置 0 映射到 4，因此逆置换中 inv[4] 必须等于 0；
• arr[1] == 0 → 位置 1 映射到 0，所以 inv[0] = 1；
• 其余位置依此类推，最终得到 inv = [1, 3, 4, 2, 0]。验证一下：inv[arr[i]] == i 对所有 i 均成立，结果正确无误。

这里有一个常见的陷阱，需要特别提醒：千万不要直接赋值引用。例如写成 origPatt = R1.Pattern; 仅仅复制了引用，后续一旦执行 R1.Pattern[...] = i，原始数据就会被覆盖。更糟糕的是，循环中再次读取 origPatt[i] 时，其值已经被提前修改，导致最终结果全部错误。正确的做法是执行深拷贝：origPatt = R1.Pattern.clone(); 或者 Arrays.copyOf(R1.Pattern, R1.Pattern.length)。

另外，一定要确保输入的 arr 是一个有效的置换——即数组长度为 n，且元素恰好是 0 到 n−1 的一个排列。否则 arr[i] 可能越界，直接抛出 ArrayIndexOutOfBoundsException 异常。

总结一下：逆置换并非排序操作，也不是简单的数组反转，其本质是构建映射函数的逆元。只要输入合法、使用独立的数组存储结果、避免引用别名陷阱，该算法的时间复杂度为 O(n)，空间复杂度为 O(n)，既稳健又高效，非常适合各类对称编解码场景，尤其是密码学轮转器中的转子映射处理。