随机列表，确保没有项目留在同一位置 [英] 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"仍然是第四项.该列表最多包含七个项目.极端效率不是考虑因素.我认为对 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];数据[j] = 数据[i];数据[i] = 温度；}}您正在寻找找到产生均匀分布紊乱的算法，对问题的一些背景，彻底的解释和分析.
第二次
实际上您的算法被称为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屋！
