音乐随机播放算法

循环播放一个歌单的时候，我觉得最难受的就是播完一首就猜到下一首是什么（循环多了是会不小心记住的）。所以我特别喜欢对歌单进行随机播放。我不知道不同的音乐播放器使用的随机播放算法具体是什么，但估计有这么几种：

1. 每次等几率地播放一首歌。这是最不近人情的算法，高中的时候有个同学的手机大概就是使用这种算法来随机播放的，歌不多时偶尔遇到播完一首又重放一遍的情形，比较恼人。
2. 播完当前曲目时，等几率播放其他曲目。这种算法不会出现重复播放一首歌的情形，但有可能两首相同的歌中间只插了一首其他歌曲。而且这种算法不能保证覆盖所有曲目，可能你放了很多歌了还是有的歌曲没有听过一遍。
3. 每次播完歌单后，打乱列表然后从头播放（顺序播放）。列表的Shuffle算法很简单也很迅速。可惜我使用的音乐播放器基本没有打乱列表的功能，不知道是出于什么考虑，可能有什么不太好的地方吧。

言归正传，如果音乐播放器能提供接口让我自己来写播放的算法，我会记录每首歌最近播放的时间，越久远则越容易被播放。例如我们的歌单里有$n$首歌，最近播放的时间分别为$t_1,t_2,\ldots,~t_n$，这里$\{t_i\}$可以直接用时间戳来记录，下一首播放歌曲$i$的几率设为$p_1,p_2,\ldots,~p_n$。$\{t_i\}$中最大的那个，就是最近播放的曲子，比如说是歌曲$k$，那我希望下面的式子成立：

$p_1:p_2:\cdots:p_n = (t_k-t_1):(t_k-t_2):\cdots:(t_k-t_n).$

这样就满足了越久远则越容易被播放这一条件，而且可以保证刚播放完的歌不会立即被播放。所以

$p_i=\frac{t_k-t_i}{\sum_{j=1}^n (t_k-t_j)}.$

写一个简单的测试例：

import random
import time

class Music:
    def __init__(self, name, author, cost_time, recentPlayTime = -1):
        self.name = name
        self.author = author
        self.time = cost_time
        self.recentPlayTime = recentPlayTime

    def Play(self):
        self.recentPlayTime = time.time()

    def __str__(self):
        return "%s - %s" % (self.name, self.author)

    
def GetNextMusic(playList):
    assert(playList)
    if len(playList) == 1:
        return playList[0]
    neverPlayed = list(filter(lambda m: m.recentPlayTime == -1, playList))
    if len(neverPlayed) > 0: # 如果还有歌从未播放过，则随机选一首播放
        return random.choice(neverPlayed)
    
    mostRecent = max(map(lambda m: m.recentPlayTime, playList))
    # 对应前文介绍的t_k

    rate = list(map(lambda m: mostRecent - m.recentPlayTime, playList))
    p = random.random() * sum(rate)
    s = 0
    for i in range(len(rate)):
        s += rate[i] 
        if s >= p:
            return playList[i]