整型数组索引与值互换实现置换逆运算方法

今天要聊聊一个看似基础但极易出错的编程操作：如何将表示置换关系的整型数组“翻转”过来，也就是构建它的逆置换。这在密码学中的轮转器实现（例如恩尼格玛仿真）里非常常见——编码和解码本质上就是一对对称的置换运算。

先理清核心概念。假设有一个数组 arr，其中 arr[i] = j 表示索引 i 映射到值 j。现在我们希望构造一个新数组 inv，使得 inv[j] = i，即交换索引与值的角色。这个操作常被称为“数组索引与值互换”或“置换求逆”，是双射函数求逆的直观体现：已知 f(i) = arr[i]，求 f⁻¹(j) = i。

举个具体的例子。假设正向映射为 [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)=2
int[] inverse = new int[original.length];

// 构造逆置换：令 inverse[original[i]] = i
for (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)，已是理论最优解，没有更快的方案。

总结起来其实就一句话：交换索引与值的本质，就是构造置换的数学逆元。牢记“以值为新索引、以原索引为新值”，同时严格分离读写内存区域，就能稳稳支撑起密码学仿真这类对确定性映射有严苛要求的场景。