今天浏览Spotify官方博客时被一篇介绍音乐随机播放算法的博客吸引，随后对这个问题小小研究了一下。
随机播放音乐，这个功能太普通以至于以前从未考虑过其背后实现逻辑。
Random还是shuffle
我们经常使用的随机播放功能，在外国同行口中并不是叫Random播放，而是叫Shuffle，洗牌的意思。
为什么不是Random？来看两个例子。
在Spotify成立之初，他们使用一种叫「Fisher-Yates shuffle」的算法去产生一个完全随机（perfectly random ）的播放列表，这个算法据说非常简单，只需3行代码搞定，不过它存在致命弱点。
上图中，每种颜色代表一位歌手，也就是说我的列表里有绿色歌手的4首歌，红色歌手的2首歌，黑色歌手的2首歌。
图中上下两行都是运行Fisher-Yates算法可能产生的播放列表，请问这两个列表出现的概率哪个更大呢？
答案是一样大，完全随机算法下，每一首歌出现在每个位置的概率是一样的。你可能认为这怎么可能，前面已经出现3次绿色歌手的歌了，下一次出现概率应该很小了吧。错了，算法是没有记忆的，除非你告诉它，下一首不允许播放绿色歌手的歌，否则它播放绿色歌手的歌的概率还是50%。
再来看个例子，假设你播放列表里有10首摇滚乐（A），11首乡村乐（B），11首爵士乐（C），下面是我自己用Python的random函数生成的序列：
A A A A C C C B C B B A C B C B B B B A B C B A C A C C A A C B
可以看出，这个列表里前半段和后半段基本上没有B出现，尤其是前面连续4个A和3个B，这样的结果是无法令人满意的，一点均衡性都没有。
回头再想，我们为什么要随机播放？因为我们不知道要听什么，我们想要一个随性的播放列表，我们不想专门听某一位歌手的或某一张专辑的曲目，我们不想按照平常循环的顺序播放，我们想换换口味有点新意，所以我们把这个选择权交给软件本身去做，如果软件接连给你播放同一个歌手或同一张专辑的曲目，那就违背我们随机的目的了。所以好的随机播放列表应该做到均衡分布，同一个流派、同一个歌手、同一种专辑下的音乐彼此之间相距越远越好。
还是上面这个例子，好的播放列表应该是下面这样的：
A B C B C A B A C B A C B C A B C A C B A B C A C B A C B C A B
shuffle播放算法
那么如何生成上面这个均衡的播放列表呢？博主Martin Fiedler给了一个思路。
1）将列表中的歌曲按流派、歌手、专辑等逻辑范式分组，给这个组里的音乐设定一个随机播放顺序；
2）接下来把每个分组的曲目通过合并算法组成一个完整的播放列表。
很简单吧，仅仅两步而已。接下来看看合并算法是怎么一回事。假设在第一步我们得到了下面的分组：
将每个分组扩充到和最大分组相等的长度，比如给绿色分组填充8首「静默」歌曲，让该组长度等于12。填充的时候应尽量让组中的音乐均衡分布列表中。
每个分组都填充完毕后，就开始合并新列表了，从每个分组的第1列按随机顺序取出歌曲放在新列表中。
再取出第2列按随机顺序取出歌曲放在新列表中。
第3列。需要注意的是，假如第2次取出的是黄-红-蓝，第3次取出蓝-黄-红-绿，那么就会有两个蓝色分组的歌曲接连出现的情况，这个时候需要把第3次拿出的歌曲首尾互换，最后得出绿-黄-红-蓝的顺序。
这就是shuffle播放背后的大概逻辑了，难的不是合并算法，而是填充分组的算法，个人感觉。
参考资料：
