您描述的方法类似于 中讨论的方法从这个破碎的随机洗牌中你得到什么分布？，但可能不完全相同。您的实现类似于井研究“从顶部到随机”洗牌（请参阅 对从上到下随机洗牌的分析，由 Diaconis、Fill 和 Pitman 撰写），最终将给出一套完全洗牌的牌组，尽管不是“一次通过”。 Top to Random shuffle的描述如下：
For Fisher-Yates, at the kth card you must choose a random number between k and 52. You are choosing a random number between 1 and 52 each time.
The method you describe is similar to that discussed in What distribution do you get from this broken random shuffle?, but may not be exactly the same. Your implementation is similar to the well studies "Top to Random" shuffle (see Analysis of Top To Random Shuffles by Diaconis, Fill and Pitman) that will eventually give a fully shuffled deck, though not in "one pass". The Top to Random shuffle is described as following:
Choose a random number p from 1 to 52, and swap the top card with the
card at position p. Continue until
the top card is the card originally in
position 52, and after this is
randomly placed the deck is in random
order.
This stop condition is known as a "Stopping Time", and takes quite a while to attain. The Fisher-Yates shuffle is far faster.
发布评论
评论（2）
这是破坏 Fisher-Yates 洗牌算法的常见方法。请参阅 您从这个损坏的随机中得到什么分布shuffle? 对此实现的属性进行了热烈的讨论。
这与 Fisher-Yates 有何不同？
对于 Fisher-Yates，在第
k卡上，您必须选择之间的随机数k和52。您每次都选择1和52之间的随机数。您描述的方法类似于 中讨论的方法从这个破碎的随机洗牌中你得到什么分布？，但可能不完全相同。您的实现类似于井研究“从顶部到随机”洗牌（请参阅 对从上到下随机洗牌的分析，由 Diaconis、Fill 和 Pitman 撰写），最终将给出一套完全洗牌的牌组，尽管不是“一次通过”。 Top to Random shuffle的描述如下：
这种停止条件被称为“停止时间”，需要相当长的时间才能达到。费舍尔-耶茨洗牌速度要快得多。
This is a common way to botch the Fisher-Yates shuffle algorithm. See What distribution do you get from this broken random shuffle? for a lively discussion on properties of this implementation.
How is this different from Fisher-Yates?
For Fisher-Yates, at the
kth card you must choose a random number betweenkand52. You are choosing a random number between1and52each time.The method you describe is similar to that discussed in What distribution do you get from this broken random shuffle?, but may not be exactly the same. Your implementation is similar to the well studies "Top to Random" shuffle (see Analysis of Top To Random Shuffles by Diaconis, Fill and Pitman) that will eventually give a fully shuffled deck, though not in "one pass". The Top to Random shuffle is described as following:
This stop condition is known as a "Stopping Time", and takes quite a while to attain. The Fisher-Yates shuffle is far faster.
是的，存在偏差，而且很容易计算。
您向随机数生成器询问 1 到 52 之间的数字 52 次。最终，这相当于 52^52 个可能的答案。
但只有52个！可能会出现洗牌的情况，因此上述算法无法使洗牌均匀分布。
您需要确保向随机数生成器询问
ld(52!)位随机性，而不是ld(52^52)。Yes, there exists a bias, and it is easy to compute.
You ask the random number generator 52 times for a number between 1 and 52. This, in the end, amounts to 52^52 possible answers.
But there are only 52! possible shuffled decks, so with the above algorithm, the shuffling cannot be evenly distributed.
You need to make sure that you ask the random number generator for
ld(52!)bits of randomness, notld(52^52).