我已经有了的 N 的项目清单。我想一个算法，让我挑选的藏品随意的潜在的无限序列，但有几个限制：

I've got a list of n items. I want an algorithm to let me pick a potentially infinite sequence of items from that collection at random, but with a couple of constraints:

一旦一个项目已被摘下来，它不应该又会出现在未来的几个项目（比方说，在未来的 M 的项目，用的 M 的明显严格＆LT; N 的） 您应该不用等太久出现任何项目 - 项目应出现在平均一次的 N 的选秀权 的顺序应该是非周期性 once an item has been picked, it shouldn't turn up again in the next few items (say in the next m items, with m obviously strictly < n) you shouldn't have to wait too long for any item to appear - items should appear on average once every n picks the sequence should be non-cyclical

基本上，我希望有一个算法来生成播放列表用于MP3播放器'洗牌'和'重复'开启，使得确保它不播放同一首歌曲太靠近自己，并确保它起着所有你的歌均匀，没有明显的模式。

Basically, I want an algorithm to generate the playlist for an MP3 player with 'shuffle' and 'repeat' turned on, that makes sure it doesn't play the same song too close to itself, and makes sure it plays all your songs evenly, with no discernible pattern.

这些制约因素消除争两个明显的解决方案：

Those constraints eliminate two obvious solutions from contention:

我们不能简单收拾RND（ N 的）作为指标的下一个项目，因为这将无法保证没有重复;它也可能需要很长的时间来挑选一些项目。 我们不能只pre-洗牌列表与费雪耶茨洗牌，并迭代它多次，每次我们到了最后一次改组它;同时，保证项目转起来后最多的 2N - 1 的选秀权，它不完全prevent项目重复。 We can't simply pick rnd(n) as the index for the next item, because that will not guarantee no repetition; it may also take a long time to pick some items. We can't just pre-shuffle the list with a Fisher-Yates shuffle, and iterate over it repeatedly, reshuffling it each time we reach the end; while that guarantees items turn up at most after 2n - 1 picks, it doesn't completely prevent an item repeating.

一个天真的解决办法可能是挑选随意，但拒绝选秀权，如果他们发生在最后的 M 的选秀权;这意味着保持的的米列表的previous选秀权，并检查各挑选针对该列表中的每个时间，这使得算法不确定的和缓慢的同时 - 两败俱伤。除非我失去了一些东西明显。

A naive solution might be to pick at random but reject picks if they occurred in the last m picks; that means keeping a list of m previous picks, and checking each pick against that list every time, which makes the algorithm nondeterministic and slow at the same time - lose-lose. Unless I'm missing something obvious..

所以，我有我有点不满意的算法，我现在使用。我用卡，在这里我有一个平局堆和弃牌堆甲板派生它类推。我的完整列表，洗牌开始，在牌堆，弃牌堆空。下一个项目是从牌堆的顶部读，然后放置在弃牌堆。一旦弃牌堆达到一定规模（ M 的项目），我将它洗，并将其移动到牌堆的底部。

So I have an algorithm I'm using now which I'm a little dissatisfied with. I've derived it by analogy with a deck of cards, where I have a draw-pile and a discard-pile. I start off with the complete list, shuffled, in the draw pile, the discard pile empty. The next item is read from the top of the draw pile, and then placed in the discard pile. Once the discard pile reaches a certain size (m items) I shuffle it, and move it to the bottom of the draw pile.

这符合要求，但洗牌一次的 M 的选秀权困扰我。这是O（1）正常，但O（M）一次的并购。这相当于一定的时间，就平均水平，但必须有一个更清洁的解决方案，打乱了丢弃的，因为它去。

This meets the requirement, but that shuffle once every m picks bothers me. It's O(1) normally, but O(m) one time in m. That amounts to constant time, on average, but there must be a cleaner solution that shuffles the discards in as it goes.

在我看来，这是这样一个简单的，通用的，普遍的问题，它必须有一个与双管算法，如费雪耶茨或博耶 - 穆尔。但我的谷歌福显然是不强的，因为我还没有找到术语集定位不可避免的1973年ACM纸，它或许可以解释究竟是如何做到这一点O（1）时间，为什么我的算法是有严重缺陷在某些方面

It seems to me that this is such a simple, generic, and common problem, it must have one of those double-barreled algorithms, like Fisher-Yates or Boyer-Moore. But my google-fu is clearly not strong, as I've yet to find the set of terms that locates the inevitable 1973 ACM paper which probably explains exactly how to do this in O(1) time, and why my algorithm is deeply flawed in some way.

推荐答案

要生成的列表请执行以下操作。有平局和弃牌堆。最初的弃牌堆是空的。选择你的第一个项目，在从牌堆随机的。将它添加到播放列表，然后把它放在弃牌堆。当有m项在弃牌，采取的最后一个项目（最近最少使用）从废堆并将其添加到拉伸桩。播放列表将是随机的，但没有洗牌需要

To generate your list do the following. Have a draw and discard pile. Initially the discard pile is empty. Pick your first item at random from the draw pile. Add it to the play list and then put it in the discard pile. When there are m items in the discard pile, take the last item (least recently used) from the discard pile and add it to the draw pile. The playlist will be random, but without shuffle required.

这是红宝石：

SONGS = [ "Pink Floyd - Wish You Were Here",
          "Radiohead - Bones",
          "Led Zeppelin - Black Dog",
          "The Cure - A Strange Day",
          "Massive Attack - Teardrop",
          "Depeche Mode - Enjoy the Silence",
          "Wilco - Jesus etc." ]

DONT_REPEAT_FOR = 3

def next_item pick, discard
  result = pick.delete_at(rand(pick.count));
  discard.push result
  pick.push(discard.shift) if (discard.count > DONT_REPEAT_FOR)
  result
end

def playlist_of_length n
    discard = []
    pick = SONGS
    playlist = []
    (0..n).each { playlist.push next_item(pick, discard) }
    playlist
end

编辑：添加playlist_of_length方法，使其更清晰，你怎么称呼NEXT_ITEM生成播放列表