如何打乱数组中每个元素的位置 ？

Question

一个数组打乱顺序，要求每个元素都不在原本的位置
看用的比较多的是洗牌算法？但是跑测试用例还是有可能某个元素没有变吧？

const fn=(arr)=>{
    for(let i=arr.length-1;i>0;i--){
        let j=Math.floor(Math.random()*(i+1));
        [arr[i],arr[j]]=[arr[j],arr[i]]
    }
    return arr
}

各位大神有什么好方法吗，算法实在是太烂...

Answer 1

之前在网上看到过类似的讨论，所以这篇回答算是“搬运”的。本着尊重原创，尊重作者的原则，在回答的开头将博客的位置放出来：

世界最速の配列シャッフルアルゴリズム、Fisher-Yatesアルゴリズム

简单的说，这是一种稍微改进的洗牌算法，称为 Fisher-Yates 算法，使用了外部的随机数源来增加随机性，这个改进的算法使用了一个 random 函数来生成随机数，确保每一次的洗牌都可以获取一个新的随机数。

const fn = (arr) => {
  const random = (min, max) => Math.floor(Math.random() * (max - min + 1)) + min;
  for (let i = arr.length - 1; i > 0; i--) {
    let j = random(0, i);
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
};

相对于目前你提到的洗牌算法，随机性更高了一些。

Answer 2

洗牌算法通常是允许元素出现在原位置的。比如 Fisher-Yates 算法，每一轮中是将当前位置的元素和后面所有位置中的一个随机位置上的元素交换，这个随机位置允许是自己所在的位置，即偏移量为 0。如果在这个算法的基础上，把偏移量为 0 的位置去掉，那么是可以保证每个元素都不在原位置上的，比如下面这个演进图

参考：从数据集中随机抽取一定数量的数据

Answer 3

function derangement(arr) {
    let n = arr.length;
    while (true) {
        let b = [...arr];
        for (let i = 0; i < n; i++) {
            let j = Math.floor(Math.random() * (n - 1));
            if (j >= i) {
                j += 1;
            }
            [b[i], b[j]] = [b[j], b[i]];
        }
        if (b.every((item, index) => item !== arr[index])) {
            return b;
        }
    }
}

Answer 4

试试洗牌算法改进版：

const shuffleArray = (arr) => {
    const shuffledArray = [...arr];
    const len = shuffledArray.length;
    for (let i = len - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [shuffledArray[i], shuffledArray[j]] = [shuffledArray[j], shuffledArray[i]];
    }
    // 检查每个元素是否在原本的位置，若在则重新洗牌
    for (let i = 0; i < len; i++) {
        if (shuffledArray[i] === arr[i]) {
            return shuffleArray(arr);
        }
    }
    return shuffledArray;
}

使用洗牌算法对副本数组进行随机重排，确保元素不在原本的位置。然后，通过遍历副本数组和原数组，检查每个元素是否在原本的位置，如果有任何一个元素在原本的位置，则重新进行洗牌，直到满足条件。