如何交换整型数组的索引与值实现置换逆运算

本文详解如何将一个表示置换的整型数组“反转”——即构建其逆置换：原数组中 arr[i] = j 表示索引 i 映射到值 j，目标是构造新数组 inv[j] = i，常用于密码学轮转器（如恩尼格玛仿真）中的编码/解码对称操作。

本文详解如何将一个表示置换的整型数组“反转”——即构建其逆置换：原数组中 `arr[i] = j` 表示索引 i 映射到值 j，目标是构造新数组 `inv[j] = i`，常用于密码学轮转器（如恩尼格玛仿真）中的编码/解码对称操作。

在实现类似恩尼格玛机器的置换逻辑时，常需对编码轮（rotor）的正向映射求逆——例如，若正向模式为 [4, 0, 3, 1, 2]（即输入 0→输出 4，输入 1→输出 0，依此类推），则其逆置换应为 [1, 3, 4, 2, 0]（即输出 0←来自输入 1，输出 1←来自输入 3，…）。这一操作本质是交换数组的索引与值角色：将原数组视为一个双射函数 f(i) = arr[i]，目标是构造 f⁻¹(j) = i。

正确实现的关键在于避免原地修改干扰遍历。常见错误是直接复用同一数组进行赋值（如 R1.Pattern[origPatt[i]] = i），而未提前保存原始状态。由于 origPatt = R1.Pattern 仅复制引用，后续写入 R1.Pattern[...] 会实时覆盖尚未读取的原始值，导致逻辑错乱。

✅ 正确做法是：

• 先创建独立副本（如使用 .clone() 或新建数组）；
• 用原始值作为新数组的索引，用原索引作为新数组的值；
• 确保原数组内容在整个循环中保持不变。

以下是安全、清晰的 Java 实现：

int[] original = {4, 0, 3, 1, 2}; // 正向置换：f(0)=4, f(1)=0, f(2)=3, f(3)=1, f(4)=2int[] inverse = new int[original.length];// 构造逆置换：令 inverse[original[i]] = ifor (int i = 0; i < original.length; i++) {    inverse[original[i]] = i;}// 输出结果：[1, 3, 4, 2, 0]System.out.println(Arrays.toString(inverse)); // [1, 3, 4, 2, 0]

⚠️ 注意事项：

• 数组必须是有效置换：original 应为 0 到 n−1 的一个排列（无重复、无越界），否则 original[i] 作为索引可能抛出 ArrayIndexOutOfBoundsException；
• 不可原地计算：切勿在 original 上直接赋值，必须使用独立的目标数组；
• 若需就地更新，应先深拷贝：int[] origCopy = R1.Pattern.clone();，再基于 origCopy 构建逆置换并写回 R1.Pattern；
• 此方法时间复杂度 O(n)，空间复杂度 O(n)，是最优解。

总结：交换索引与值的本质是构建置换的数学逆元。牢记“以值为新索引、以原索引为新值”，并严格分离读写内存区域，即可稳健支持密码学仿真等对确定性映射有严格要求的场景。