algorithm - 如何实现随机的重复洗牌 - 但不是太随机

Question

我有一个包含 n 个项目的列表。我想要一个算法让我从该集合中随机选择一个可能无限的项目序列，但有几个限制:

1. 一旦一个项目被选中，它不应该在接下来的几个项目中再次出现(比如在接下来的 m 个项目中，m 显然严格 << em>n)
2. 您不必等待任何元素出现太久 - 元素应该平均每 n 次出现一次
3. 序列应该是非循环的

基本上，我想要一种算法来为打开“随机播放”和“重复播放”的 MP3 播放器生成播放列表，以确保它不会播放同一首歌曲离自己太近，并确保播放所有歌曲你的歌曲均匀，没有明显的模式。

这些限制从争论中排除了两个明显的解决方案:

• 我们不能简单地选择 rnd(n) 作为下一项的索引，因为那样不能保证不重复；挑选一些元素也可能需要很长时间。
• 我们不能只使用 Fisher-Yates 洗牌法预先洗牌，然后反复迭代，每次到达末尾时重新洗牌；虽然这保证了元素最多在 2n - 1 次选择后出现，但它并不能完全防止元素重复出现。

一个天真的解决方案可能是随机选择，但拒绝出现在最后 m 个选择中的选择；这意味着保留一个包含 m 个先前选择的列表，并每次都根据该列表检查每个选择，这使得算法具有不确定性，同时速度很慢 - 双输。除非我遗漏了一些明显的东西..

所以我有一个我现在使用的算法，我有点不满意。我用一副纸牌类比得出它，我有一个抽牌堆和一个弃牌堆。我从完整的列表开始，在抽牌堆中洗牌，弃牌堆是空的。从抽牌堆的顶部读取下一个项目，然后将其放入弃牌堆。一旦弃牌堆达到一定大小(m 项)，我将其洗牌，然后将其移到抽牌堆的底部。

这符合要求，但每 m 次选择洗牌让我很困扰。通常是 O(1)，但在 m 中一次是 O(m)。平均而言，这相当于常数时间，但必须有一个更清洁的解决方案，可以在丢弃的过程中洗牌。

在我看来，这是一个如此简单、通用且常见的问题，它必须具有那些双管算法之一，例如 Fisher-Yates 或 Boyer-Moore。但我的 google-fu 显然不强大，因为我还没有找到定位不可避免的 1973 年 ACM 论文的术语集，它可能解释了如何在 O(1) 时间内做到这一点，以及为什么我的算法存在严重缺陷以某种方式。

Answer 1

要生成列表，请执行以下操作。有一个平局和弃牌堆。最初，弃牌堆是空的。从抽牌堆中随机挑选您的第一个项目。将其添加到播放列表，然后将其放入弃牌堆。当弃牌堆中有 m 件元素时，从弃牌堆中取出最后一件(最近最少使用的)元素并将其添加到抽牌堆中。播放列表将是随机的，但不需要随机播放。

这是 ruby 的:

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 来生成播放列表