如何实现JavaScript数组错位洗牌函数？无元素保留原索引

普通的Fisher-Yates洗牌是均匀随机的，但无法保证所有元素都不在原索引位置（这种排列称为「错位排列/Derangement」）。下面提供两种可靠的实现方案：

方案一：改造Fisher-Yates算法（O(n)时间复杂度） #

通过调整交换逻辑，从根源避免元素留在原位：

function derangeShuffle(array) {
  // 先复制原数组，避免修改输入的原始数据
  const arr = [...array];
  let m = arr.length;

  // 处理长度为1的特殊情况（无法错位）
  if (m === 1) return arr;

  while (m > 1) {
    // 随机选择[0, m-2]范围内的索引，确保不选中当前要处理的m-1位置
    const i = Math.floor(Math.random() * (m - 1));
    // 交换当前末尾元素和随机选中的元素
    [arr[m - 1], arr[i]] = [arr[i], arr[m - 1]];
    m--;
  }

  // 最后检查第一个元素，如果和原数组第一个元素重合，交换它和最后一个元素
  if (arr[0] === array[0]) {
    const lastIdx = arr.length - 1;
    [arr[0], arr[lastIdx]] = [arr[lastIdx], arr[0]];
  }

  return arr;
}

逻辑说明： #

• 循环过程中，每次处理倒数第m个元素时，只从前面的m-1个位置选交换目标，确保当前元素不会留在原位
• 最后一步检查第一个元素是为了避免极端情况（比如前n-1个元素都错位，但第一个元素刚好和原数组一致）

方案二：洗牌后校验（简单易实现，适合小数组） #

如果数组长度不大，直接用Fisher-Yates洗牌后校验是否符合错位要求，不符合就重新洗牌：

function derangeShuffleSimple(array) {
  const arr = [...array];
  const original = [...array];
  let isValid = false;

  // 处理长度为1的特殊情况
  if (arr.length === 1) return arr;

  while (!isValid) {
    // 执行标准Fisher-Yates洗牌
    let m = arr.length;
    while (m) {
      const i = Math.floor(Math.random() * m--);
      [arr[m], arr[i]] = [arr[i], arr[m]];
    }
    // 校验所有元素是否都不在原位置
    isValid = arr.every((val, idx) => val !== original[idx]);
  }

  return arr;
}

逻辑说明： #

• 错位排列的概率随着数组长度增加趋近于1/e（约36.8%），所以循环次数不会太多，实际效率足够
• 代码实现简单，容易理解和调试

测试示例 #

const original = [0, 1, 2, 3, 4, 5];
const shuffled = derangeShuffle(original);
console.log(shuffled); // 示例输出：[4, 2, 5, 0, 1, 3]
console.log(shuffled.every((val, idx) => val !== original[idx])); // 输出：true

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