小编Jam*_*art的帖子

我有一份n项清单.我想要一个算法让我随机从该集合中选择一个可能无限的项目序列,但有几个约束条件:

1. 一旦一个项目被挑选,它不应该在接下来的几个项目中再次出现(比如在接下来的m个项目中,m显然严格< n)
2. 你不应该等待很长时间,任何项目出现-项目应该出现,平均每一次ñ精选
3. 序列应该是非周期性的

基本上,我想要一个算法为MP3播放器生成播放列表,打开'shuffle'和'repeat',这样可以确保它不会播放太靠近自己的同一首歌,并确保它能均匀播放所有歌曲,没有明显的模式.

这些限制消除了争用的两个明显的解决方案:

• 我们不能简单地选择rnd(n)作为下一个项目的索引,因为这不能保证不重复; 选择一些物品也可能需要很长时间.
• 我们不能只用Fisher-Yates shuffle对列表进行预先洗牌,并反复迭代它,每次我们到达终点时重新洗牌; 虽然保证物品在2n - 1次挑选后最多出现,但它并不能完全阻止物品重复.

一个天真的解决方案可能是随机挑选,但拒绝选秀权,如果他们发生在上米选秀权; 这意味着保留m个先前选择的列表,并且每次都对该列表检查每个选择,这使得算法不确定并且同时变慢 - 失败.除非我遗漏了一些明显的东西......

所以我有一个我正在使用的算法,我有点不满意.我用一副牌来比喻它,我有一个画堆和弃牌堆.我从完整的清单开始,洗牌,在抽签堆中,丢弃堆空.从绘图堆的顶部读取下一个项目,然后放入丢弃堆中.一旦丢弃堆达到一定的尺寸(m项),我就将它移动,并将其移动到拉桩的底部.

这符合要求,但是这一次洗牌每米挑选困扰我.通常是O(1),但是m(m)一次是O(m).平均而言,这相当于一个恒定的时间,但必须有一个更清洁的解决方案,随着时间的推移丢弃丢弃物.

在我看来,这是一个如此简单,通用和常见的问题,它必须具有其中一种双管算法,如Fisher-Yates或Boyer-Moore.但是我的谷歌显然并不强大,因为我还没有找到定位不可避免的1973年ACM论文的术语集,这些论文可能解释了在O(1)时间内如何做到这一点,以及为什么我的算法存在严重缺陷某种程度上来说.