什么是一个很好的通伪随机洗牌？ [英] What's a good one-pass pseudo-random shuffle?

问题描述

借助费雪耶茨洗牌给出了一个很好的算法洗牌的数组 A 在一个单一的传球长度 N 的：

The Fisher-Yates shuffle gives a nice algorithm to shuffle an array A of length n in a single pass:

For k = 1 to n
    Pick a random integer j from k to n
    Swap A[k] and A[j]

在通过该算法单传中， A 均匀地发生随机的条目。

After a single pass through this algorithm, the entries of A occur uniformly at random.

要误事该算法的常用方法是做到以下几点：

A common way to botch this algorithm is to do the following:

For k = 1 to n
    Pick a random integer j from 1 to n
    Swap A[k] and A[j]

从一次性通过这种算法得到的分布的不可以均匀随机的，有什么是在这个职位一个很好的讨论：<一href="http://stackoverflow.com/questions/5131341/what-distribution-do-you-get-from-this-broken-random-shuffle">What分配你从这个破碎的随机洗牌得到什么呢？

The resulting distribution from a single pass through this algorithm is not uniformly random, and there is a nice discussion of what it is at this post: What distribution do you get from this broken random shuffle?

我最近看了一个愉快的文章戴康尼斯，Fulman福尔摩斯有权赌场架洗牌机其中分析作者描述物理机，做如下的批处理洗牌：

I recently read a delightful article by Diaconis, Fulman and Holmes entitled Analysis of Casino Shelf Shuffling Machines where the authors describe a physical machine that does the following batch shuffle:

For k = 1 to n
    Pick a random integer j from 1 to 10
    Randomly choose to place card k on the top or bottom of stack j

问题提交解决的是这是否给出了一个单一的传球后一个合理的随机排序。答案是决然不会。看到该缺陷在这个洗牌的一种方法是先从一副扑克牌有 N / 2 红牌之上的 N / 2 黑卡。单传后，由此产生的甲板将有至多10团块红牌！对于 N = 52 * 6 ，这是不是非常随机的。作者还显示的最佳猜测下一张牌战略的一次洗牌的意志，平均猜9.5卡，而对于随机甲板的最优策略将平均只有4.5卡猜对了。

The question the authors address is whether or not this gives a reasonably random ordering after a single pass. The answer is decidedly not. One way to see the flaw in this shuffle is to start with a deck of cards that has n/2 red cards atop of n/2 black cards. The resulting deck after a single pass will have at most 10 clumps of red cards! For n = 52*6, this isn't terribly random. The authors also show that an optimal "guess the next card" strategy for the once shuffled will, on average, correctly guess 9.5 cards, whereas an optimal strategy for a random deck will average only 4.5 cards correctly guessed.

这附近是否有随机性和/或有趣的分布是实现任何其他有趣的单次洗牌？我在慢腾腾类似于后者，随着项目的批工作特别感兴趣。

Are there any other interesting single-pass shuffles that achieve near-randomness and/or interesting distributions? I'm especially interested in shuffles similar to the latter that work with batches of entries.

推荐答案

如果你有一个洗牌的办公桌，在其中你想洗牌了一批新卡（你知道，没有任何的卡是重复的），那么我认为以下是有效的。

If you have a shuffled desk, into which you wish to shuffle a batch of new cards (and you know that none of the cards are duplicates), then I think the following is valid.

ForEach card in batch:
    gap = random(deck.size() + 1)  # choose a gap between cards, before first, or after last.
    deck.insertAt(gap,card)

分布

随机的分布是均匀的，和甲板的顺序是不变的，所以仍然均匀。 我想结果应该是一致的。 （我的统计是太生疏，以确保）。

The distribution of random is uniform, and the order of the deck is unchanged, so still uniform. I think the result should be uniform. (My stats is too rusty to be sure).

时间

假设insertAt是O（1）不是O（N） - 这取决于甲板的implementeation - 整个程序是O（批量） - 这是最好的，你可以希望监守你必须处理每一张卡

Assuming that insertAt is O(1) not O(N) - which depends upon the implementeation of deck - the whole routine is O(batch size) - which is the best you can hope for becuase you have to handle each card.

这篇关于什么是一个很好的通伪随机洗牌？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！