algorithm - 洗牌列表，确保没有项目留在同一位置

Question

我想洗牌一个独特的项目列表，但不是完全随机洗牌。我需要确保打乱后的列表中没有元素与原始列表中的位置相同。因此，如果原始列表是 (A, B, C, D, E)，则此结果是可以的:(C, D, B, E, A)，但这个结果不是:(C, E, A, D, B) 因为“D”仍然是第四项。该列表最多包含七个项目。极端效率不是考虑因素。我认为对 Fisher/Yates 的这种修改可以解决问题，但我无法从数学上证明它:

function shuffle(data) {
    for (var i = 0; i < data.length - 1; i++) {
        var j = i + 1 + Math.floor(Math.random() * (data.length - i - 1));

        var temp = data[j];
        data[j] = data[i];
        data[i] = temp;
    }
}

Answer 1

您正在寻找 derangement您的条目。

首先，您的算法的工作原理是它输出随机紊乱，即没有不动点的排列。然而，它有一个巨大的缺陷(您可能不介意，但值得牢记):您的算法无法获得某些紊乱。换句话说，它给一些可能的紊乱概率为零，所以最终的分布绝对不是均匀随机的。

如评论中所建议的，一种可能的解决方案是使用拒绝算法:

• 随机均匀地选择一个排列
• 如果没有固定点，返回
• 否则重试

渐近地，获得紊乱的概率接近于 1/e = 0.3679(如维基百科文章中所示)。这意味着要获得紊乱，您需要平均生成 e = 2.718 个排列，这是非常昂贵的。

更好的方法是在算法的每一步 拒绝。在伪代码中，类似这样的事情(假设原始数组在 i 位置包含 i，即 a[i]==i):

for (i = 1 to n-1) {
   do {
      j = rand(i, n)   // random integer from i to n inclusive
   } while a[j] != i   // rejection part
   swap a[i] a[j]
}

与您的算法的主要区别在于我们允许 j 等于 i，但前提是它不产生不动点。执行时间略长(由于拒绝部分)，并且要求您能够检查条目是否在其原始位置，但它的优点是它可以产生所有可能的困惑(统一地，为此事)。

我猜不拒绝算法应该存在，但我相信它们不那么直接。

编辑:

我的算法实际上很糟糕:你仍然有机会以未打乱的最后一个点结束，而且分布根本不是随机的，请参见模拟的边际分布:

可以找到一种产生均匀分布紊乱的算法 here , 对问题有一些背景，透彻的解释和分析。

第二次编辑:

实际上你的算法被称为Sattolo's algorithm ，并且已知以相等的概率产生所有循环。因此，任何不是循环而是几个不相交循环的乘积的紊乱都无法用该算法获得。例如，有四个元素，交换1和2，交换3和4的排列是排列而不是循环。

如果您不介意只获得循环，那么 Sattolo 的算法是可行的方法，它实际上比任何统一的紊乱算法都快得多，因为不需要拒绝。