随机播放列表，确保没有项目保持在相同的位置 [英] Shuffle list, ensuring that no item remains in same position

问题描述

我想洗牌的唯一项目列表，但不是做一个完全随机的洗牌。我需要确保在混洗表中没有元件是在相同的位置在原始列表。因此，如果原来的列表（A，B，C，D，E），这个结果将是确定：（C，D，B，E，A），但是这个不会：（C，E，A， D，B），因为D仍是第四个项目。列表将具有至多7项。至尊效率不是一个考虑因素。我觉得这个修改费舍尔/耶茨的伎俩，但我不能证明这一点数学：

 函数洗牌（数据）{
    对于（VAR I = 0; I＆LT; data.length  -  1;我++）{
        变种J = 1 + 1 + Math.floor（的Math.random（）*（data.length  -  I  -  1））;

        变种临时=数据[J]。
        数据[J] =数据[I]
        数据[i] =气温;
    }
}
 

解决方案

您正在寻找您的条目紊乱

首先，你的算法工作在它输出一个随机紊乱，即没有确定的点的置换感。但是它有一个巨大的缺陷（你可能不介意，但值得记住）：有些紊乱，不能用你的算法获得。换句话说，它给出概率零到一些可能的紊乱，所以所得到的分布是绝对不能均匀随机

一种可能的解决方案，因为在意见认为，将是利用一个拒绝的算法：

• 统一接一个排列，随机
• 如果它HAX没有固定点，其返回
• ，否则重试

渐近，获得紊乱的概率接近 1 / E = 0.3679（如维基百科的文章中看到的）。这意味着，要获得紊乱，你需要生成的平均电子商务 = 2.718置换，这是相当昂贵的。

一个更好的方式来做到这一点会在算法的每一步的拒绝的。在伪code，像这样（假设原数组包含我在位置我，即 A [1] ==我）：

 为（i = 1至N-1）{
   做 {
      J =兰特（I，N）//随机整数从我到n包容
   }而[J]！= I //抑制部分
   换一个[我]一个[J]。
}
 

这是你的算法的主要区别是，我们让Ĵ等于我，但只有当它不会产生一个固定点。它略长执行（由于排斥部分），并要求你能够检查条目是否是在其原始位置或没有，但它有，它可以产生每一个可能的紊乱的优点（均匀地，该物）。

我猜不抑制算法应该存在，但我相信他们不那么简单。

编辑：

我的算法其实是不好的：你仍然有最后一点unshuffled结束的机会，且分布不是随机的，在所有的，看到一个模拟的边缘分布：

这会产生均匀分布紊乱的算法，可以发现此处，搭配上一些背景问题，全面的讲解和分析。

第二个编辑：

实际上你的算法被称为 Sattolo算法的，并且已知生产等概率的所有周期。所以任何紊乱这不是一个周期，但不相交的几个周期的产品不能用算法获得。例如，具有四个元件，即交换1和2，以及3和4的排列是紊乱但不是一个循环

如果你不介意仅获得循环，然后Sattolo的算法是要走的路，这比任何制服紊乱的算法实际上要快得多，因为没有排斥反应是必要的。

I want to shuffle a list of unique items, but not do an entirely random shuffle. I need to be sure that no element in the shuffled list is at the same position as in the original list. Thus, if the original list is (A, B, C, D, E), this result would be OK: (C, D, B, E, A), but this one would not: (C, E, A, D, B) because "D" is still the fourth item. The list will have at most seven items. Extreme efficiency is not a consideration. I think this modification to Fisher/Yates does the trick, but I can't prove it mathematically:

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;
    }
}

解决方案

You are looking for a derangement of your entries.

First of all, your algorithm works in the sense that it outputs a random derangement, ie a permutation with no fixed point. However it has a enormous flaw (which you might not mind, but is worth keeping in mind): some derangements cannot be obtained with your algorithm. In other words, it gives probability zero to some possible derangements, so the resulting distribution is definitely not uniformly random.

One possible solution, as suggested in the comments, would be to use a rejection algorithm:

• pick a permutation uniformly at random
• if it hax no fixed points, return it
• otherwise retry

Asymptotically, the probability of obtaining a derangement is close to 1/e = 0.3679 (as seen in the wikipedia article). Which means that to obtain a derangement you will need to generate an average of e = 2.718 permutations, which is quite costly.

A better way to do that would be to reject at each step of the algorithm. In pseudocode, something like this (assuming the original array contains i at position i, ie 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]
}

The main difference from your algorithm is that we allow j to be equal to i, but only if it does not produce a fixed point. It is slightly longer to execute (due to the rejection part), and demands that you be able to check if an entry is at its original place or not, but it has the advantage that it can produce every possible derangement (uniformly, for that matter).

I am guessing non-rejection algorithms should exist, but I would believe them to be less straight-forward.

Edit:

My algorithm is actually bad: you still have a chance of ending with the last point unshuffled, and the distribution is not random at all, see the marginal distributions of a simulation:

An algorithm that produces uniformly distributed derangements can be found here, with some context on the problem, thorough explanations and analysis.

Second Edit:

Actually your algorithm is known as Sattolo's algorithm, and is known to produce all cycles with equal probability. So any derangement which is not a cycle but a product of several disjoint cycles cannot be obtained with the algorithm. For example, with four elements, the permutation that exchanges 1 and 2, and 3 and 4 is a derangement but not a cycle.

If you don't mind obtaining only cycles, then Sattolo's algorithm is the way to go, it's actually much faster than any uniform derangement algorithm, since no rejection is needed.

这篇关于随机播放列表，确保没有项目保持在相同的位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！