如何在Java中随机打乱数组且保证无元素处于原始位置

你需要实现的是错排（Derangement），即不存在任何元素位于其原始索引位置的排列。

现有代码问题分析 #

• 递归逻辑存在缺陷：遍历数组时只要发现一个元素位于原位就立刻递归重排，递归后没有重新校验整个数组，数组长度较大时还可能出现栈溢出，执行效率极低。
• 每次调用都创建新的Random实例，短时间多次调用会因为种子重复导致随机结果均匀性差。
• 未处理边界情况：当数组长度为1时不存在符合要求的错排，现有代码会进入无限递归。

优化实现方案 #

方案一：拒绝采样（均匀分布，实现简单） #

该方案基于Fisher-Yates洗牌算法，生成随机排列后校验是否符合错排要求，不符合则重试，生成的所有错排概率均匀，适合绝大多数业务场景：

// 复用Random实例，不要每次方法内创建
private final Random random = new Random();

private int[] shuffleIndex() {
    int size = cards.length;
    // 长度为1时无合法错排，可根据业务需求调整处理逻辑
    if (size == 1) {
        throw new IllegalStateException("数组长度为1时无法生成符合要求的错排");
    }
    int[] numberList = new int[size];
    for(int i = 0; i < size; i++) {
        numberList[i] = i;
    }
    randomizer(numberList);
    return numberList;
}
    
private void randomizer(int[] input) {
    int size = input.length;
    while (true) {
        // Fisher-Yates 标准洗牌算法
        for (int i = size - 1; i > 0; i--) {
            int j = random.nextInt(i + 1);
            int temp = input[i];
            input[i] = input[j];
            input[j] = temp;
        }
        // 校验是否符合错排要求
        boolean isDerangement = true;
        for (int i = 0; i < size; i++) {
            if (input[i] == i) {
                isDerangement = false;
                break;
            }
        }
        if (isDerangement) {
            return;
        }
    }
}

数组长度大于2时，错排的概率约为1/e≈37%，平均只要重试2~3次就能得到合法结果，性能完全满足常规需求。

方案二：直接生成错排（无需重试，性能更高） #

如果对性能要求极高，可以用修改版的Fisher-Yates算法，交换时永远不和当前位置自身交换，直接生成错排，缺点是生成的错排不是均匀分布的：

private void randomizer(int[] input) {
    int size = input.length;
    for (int i = size - 1; i > 0; i--) {
        // 随机索引范围为0~i-1，避免和自身交换
        int j = random.nextInt(i);
        int temp = input[i];
        input[i] = input[j];
        input[j] = temp;
    }
}

内容的提问来源于stack exchange，提问作者GS1221