如何实现随机的重复随机播放 - 但不是太随机
Jam*_*art 19 random algorithm shuffle
我有一份n项清单.我想要一个算法让我随机从该集合中选择一个可能无限的项目序列,但有几个约束条件:
- 一旦一个项目被挑选,它不应该在接下来的几个项目中再次出现(比如在接下来的m个项目中,m显然严格< n)
- 你不应该等待很长时间,任何项目出现-项目应该出现,平均每一次ñ精选
- 序列应该是非周期性的
基本上,我想要一个算法为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)时间内如何做到这一点,以及为什么我的算法存在严重缺陷某种程度上来说.
Dea*_*vey 12
要生成列表,请执行以下操作.有一个平局和丢弃堆.最初丢弃堆是空的.从绘图堆中随机选择您的第一个项目.将其添加到播放列表中,然后将其放入丢弃堆中.当有弃牌堆m个,从弃牌堆取最后一个项目(最近最少使用),并把它添加到牌堆.播放列表将是随机的,但不需要随机播放.
这是红宝石:
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以生成播放列表
除了队列算法实现和可视化验证
在Mathematica中:
Play[themes_, minCycle_, iterations_] :=
Module[{l, queue, played},
l = Range[themes];
queue = {};
played = {}; (*just for accounting*)
While [ Length@played < iterations,
(AppendTo[queue, #]; l = DeleteCases[l, #]) &@RandomChoice[l];
If[Length[queue] > minCycle, (AppendTo[l, First@queue]; queue = Rest@queue)];
AppendTo[played, Last@queue]
];
Return[played];
]
MatrixPlot[Partition[Play[100, 50, 20000], 100], ColorFunction -> Hue]
让我们看看没有明显的重复模式:
比较不同的周期长度:
播放给定的歌曲后,使用伪附加将其放在列表的末尾附近.您可能希望在列表中的最后5个左右的项目中真正附加1/2到2/3并且另外1/3到1/2的差异.
显然这对于非常短的列表不起作用,但对于10个或更多的列表应该没问题.
编辑(提供有关'PseudoAppend'的更多详细信息):
下面的伪代码使用了混合的语言结构,但应该很容易变成真正的代码.
给定列表[歌曲]
While(PLAY)
Play(List[0])
PseudoAppend(List[], 0)
def PseudoAppend(List[], index)
# test to verify length of list, valid index, etc.
song = List[index].delete # < not safe
List.append(song)
target = -1
While( (random() < (1/3)) && (target > -3) )
Swap(List[target], List[target-1])
target -= 1
在没有备份列表的情况下从列表中删除刚刚完成的歌曲可能会导致信息丢失,但这只是用于表达想法的伪代码.
正如您所看到的,刚刚播放的歌曲的2/3时间将移动到列表的后面,并且1/3的时间将移动到最后一首歌曲的前面.
在该歌曲向前移动的1/3的机会中,2/3的时间它只会在一首歌曲之前移动,而另外1/3的时间它将在两首或更多的歌曲之前移动.歌曲移动到最后位置的机会= 66%,倒数第二位置= 22%,倒数第三位= 12%.
PseudoAppend的实际行为都在While语句的条件下进行控制.您可以更改要与random数字生成器进行比较的值,以使歌曲或多或少地移动到其他人之前,并且您可以更改相对的值target以调整刚完成的歌曲在列表中向前移动的距离.
编辑II(Python 3代码和示例输出以获取11个项目的列表)
songlist=[0,1,2,3,4,5,6,7,8,9,10]
import random
def pseudoappend(locallist, index):
song=locallist[index]
del(locallist[index])
locallist.append(song)
target=-1
while (random.randint(1,3)==1) and (target> -3):
locallist[target],locallist[target-1] = locallist[target-1],locallist[target]
target-=1
for x in range(len(songlist)*9):
print("%3d" % x, ': ', "%2d" % songlist[0], ': ', songlist)
pseudoappend(songlist, 0)
print( 'end : ', "%2d" % songlist[0], ': ', songlist)
这是一个在列表中运行〜9次的示例输出.第一列只是一个运行索引,第二列显示当前选定的歌曲,第三列显示列表的当前顺序:
>>> ================================ RESTART ================================
>>>
0 : 0 : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
1 : 1 : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0]
2 : 2 : [2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1]
3 : 3 : [3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2]
4 : 4 : [4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3]
5 : 5 : [5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4]
6 : 6 : [6, 7, 8, 9, 10, 0, 1, 2, 3, 4, 5]
7 : 7 : [7, 8, 9, 10, 0, 1, 2, 3, 4, 5, 6]
8 : 8 : [8, 9, 10, 0, 1, 2, 3, 4, 5, 6, 7]
9 : 9 : [9, 10, 0, 1, 2, 3, 4, 5, 6, 7, 8]
10 : 10 : [10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
11 : 0 : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
12 : 1 : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0]
13 : 2 : [2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 0]
14 : 3 : [3, 4, 5, 6, 7, 8, 9, 10, 1, 0, 2]
15 : 4 : [4, 5, 6, 7, 8, 9, 10, 1, 0, 2, 3]
16 : 5 : [5, 6, 7, 8, 9, 10, 1, 0, 2, 3, 4]
17 : 6 : [6, 7, 8, 9, 10, 1, 0, 2, 3, 4, 5]
18 : 7 : [7, 8, 9, 10, 1, 0, 2, 3, 4, 6, 5]
19 : 8 : [8, 9, 10, 1, 0, 2, 3, 4, 6, 7, 5]
20 : 9 : [9, 10, 1, 0, 2, 3, 4, 6, 7, 5, 8]
21 : 10 : [10, 1, 0, 2, 3, 4, 6, 7, 5, 8, 9]
22 : 1 : [1, 0, 2, 3, 4, 6, 7, 5, 10, 8, 9]
23 : 0 : [0, 2, 3, 4, 6, 7, 5, 10, 8, 9, 1]
24 : 2 : [2, 3, 4, 6, 7, 5, 10, 8, 9, 1, 0]
25 : 3 : [3, 4, 6, 7, 5, 10, 8, 9, 2, 1, 0]
26 : 4 : [4, 6, 7, 5, 10, 8, 9, 2, 1, 0, 3]
27 : 6 : [6, 7, 5, 10, 8, 9, 2, 1, 0, 3, 4]
28 : 7 : [7, 5, 10, 8, 9, 2, 1, 0, 3, 4, 6]
29 : 5 : [5, 10, 8, 9, 2, 1, 0, 3, 4, 6, 7]
30 : 10 : [10, 8, 9, 2, 1, 0, 3, 4, 5, 6, 7]
31 : 8 : [8, 9, 2, 1, 0, 3, 4, 5, 10, 6, 7]
32 : 9 : [9, 2, 1, 0, 3, 4, 5, 10, 6, 7, 8]
33 : 2 : [2, 1, 0, 3, 4, 5, 10, 6, 7, 9, 8]
34 : 1 : [1, 0, 3, 4, 5, 10, 6, 7, 9, 8, 2]
35 : 0 : [0, 3, 4, 5, 10, 6, 7, 9, 8, 2, 1]
36 : 3 : [3, 4, 5, 10, 6, 7, 9, 8, 2, 1, 0]
37 : 4 : [4, 5, 10, 6, 7, 9, 8, 2, 1, 0, 3]
38 : 5 : [5, 10, 6, 7, 9, 8, 2, 1, 0, 3, 4]
39 : 10 : [10, 6, 7, 9, 8, 2, 1, 0, 3, 4, 5]
40 : 6 : [6, 7, 9, 8, 2, 1, 0, 3, 4, 5, 10]
41 : 7 : [7, 9, 8, 2, 1, 0, 3, 4, 5, 10, 6]
42 : 9 : [9, 8, 2, 1, 0, 3, 4, 5, 7, 10, 6]
43 : 8 : [8, 2, 1, 0, 3, 4, 5, 7, 10, 6, 9]
44 : 2 : [2, 1, 0, 3, 4, 5, 7, 10, 6, 9, 8]
45 : 1 : [1, 0, 3, 4, 5, 7, 10, 6, 2, 9, 8]
46 : 0 : [0, 3, 4, 5, 7, 10, 6, 2, 9, 8, 1]
47 : 3 : [3, 4, 5, 7, 10, 6, 2, 9, 8, 1, 0]
48 : 4 : [4, 5, 7, 10, 6, 2, 9, 8, 1, 3, 0]
49 : 5 : [5, 7, 10, 6, 2, 9, 8, 1, 3, 0, 4]
50 : 7 : [7, 10, 6, 2, 9, 8, 1, 3, 5, 0, 4]
51 : 10 : [10, 6, 2, 9, 8, 1, 3, 5, 0, 7, 4]
52 : 6 : [6, 2, 9, 8, 1, 3, 5, 0, 7, 4, 10]
53 : 2 : [2, 9, 8, 1, 3, 5, 0, 7, 6, 4, 10]
54 : 9 : [9, 8, 1, 3, 5, 0, 7, 6, 4, 10, 2]
55 : 8 : [8, 1, 3, 5, 0, 7, 6, 4, 10, 2, 9]
56 : 1 : [1, 3, 5, 0, 7, 6, 4, 10, 2, 9, 8]
57 : 3 : [3, 5, 0, 7, 6, 4, 10, 2, 9, 1, 8]
58 : 5 : [5, 0, 7, 6, 4, 10, 2, 9, 3, 1, 8]
59 : 0 : [0, 7, 6, 4, 10, 2, 9, 3, 1, 8, 5]
60 : 7 : [7, 6, 4, 10, 2, 9, 3, 1, 8, 5, 0]
61 : 6 : [6, 4, 10, 2, 9, 3, 1, 8, 5, 0, 7]
62 : 4 : [4, 10, 2, 9, 3, 1, 8, 5, 0, 7, 6]
63 : 10 : [10, 2, 9, 3, 1, 8, 5, 0, 7, 6, 4]
64 : 2 : [2, 9, 3, 1, 8, 5, 0, 7, 6, 4, 10]
65 : 9 : [9, 3, 1, 8, 5, 0, 7, 6, 4, 10, 2]
66 : 3 : [3, 1, 8, 5, 0, 7, 6, 4, 10, 2, 9]
67 : 1 : [1, 8, 5, 0, 7, 6, 4, 10, 2, 9, 3]
68 : 8 : [8, 5, 0, 7, 6, 4, 10, 2, 9, 3, 1]
69 : 5 : [5, 0, 7, 6, 4, 10, 2, 9, 8, 3, 1]
70 : 0 : [0, 7, 6, 4, 10, 2, 9, 8, 3, 1, 5]
71 : 7 : [7, 6, 4, 10, 2, 9, 8, 3, 0, 1, 5]
72 : 6 : [6, 4, 10, 2, 9, 8, 3, 0, 1, 5, 7]
73 : 4 : [4, 10, 2, 9, 8, 3, 0, 1, 5, 7, 6]
74 : 10 : [10, 2, 9, 8, 3, 0, 1, 5, 7, 6, 4]
75 : 2 : [2, 9, 8, 3, 0, 1, 5, 7, 6, 4, 10]
76 : 9 : [9, 8, 3, 0, 1, 5, 7, 6, 4, 10, 2]
77 : 8 : [8, 3, 0, 1, 5, 7, 6, 4, 10, 2, 9]
78 : 3 : [3, 0, 1, 5, 7, 6, 4, 10, 2, 9, 8]
79 : 0 : [0, 1, 5, 7, 6, 4, 10, 2, 3, 9, 8]
80 : 1 : [1, 5, 7, 6, 4, 10, 2, 3, 9, 8, 0]
81 : 5 : [5, 7, 6, 4, 10, 2, 3, 9, 8, 1, 0]
82 : 7 : [7, 6, 4, 10, 2, 3, 9, 8, 1, 0, 5]
83 : 6 : [6, 4, 10, 2, 3, 9, 8, 1, 0, 7, 5]
84 : 4 : [4, 10, 2, 3, 9, 8, 1, 0, 7, 5, 6]
85 : 10 : [10, 2, 3, 9, 8, 1, 0, 7, 5, 6, 4]
86 : 2 : [2, 3, 9, 8, 1, 0, 7, 5, 6, 4, 10]
87 : 3 : [3, 9, 8, 1, 0, 7, 5, 6, 4, 2, 10]
88 : 9 : [9, 8, 1, 0, 7, 5, 6, 4, 2, 10, 3]
89 : 8 : [8, 1, 0, 7, 5, 6, 4, 2, 10, 3, 9]
90 : 1 : [1, 0, 7, 5, 6, 4, 2, 10, 8, 3, 9]
91 : 0 : [0, 7, 5, 6, 4, 2, 10, 8, 3, 1, 9]
92 : 7 : [7, 5, 6, 4, 2, 10, 8, 3, 1, 9, 0]
93 : 5 : [5, 6, 4, 2, 10, 8, 3, 1, 9, 0, 7]
94 : 6 : [6, 4, 2, 10, 8, 3, 1, 9, 0, 7, 5]
95 : 4 : [4, 2, 10, 8, 3, 1, 9, 0, 7, 6, 5]
96 : 2 : [2, 10, 8, 3, 1, 9, 0, 7, 6, 4, 5]
97 : 10 : [10, 8, 3, 1, 9, 0, 7, 6, 4, 5, 2]
98 : 8 : [8, 3, 1, 9, 0, 7, 6, 4, 5, 2, 10]
end : 3 : [3, 1, 9, 0, 7, 6, 4, 5, 2, 10, 8]