我在设计算法以帮助创建mp3播放列表时遇到了麻烦,尽管针对列表中项目均匀分布的更一般情况的算法可能适合我的使用。
一般情况是,我想对列表中的项目进行重新排序,以使它们在多个轴上的多样性最大化。
我的特定用例是,我想将一堆歌曲转储到一个集合中,然后在该集合上运行我的算法以生成一个有序的播放列表。我希望订单遵循以下标准:
显然,我们不能保证对所有类别进行均等的优化,因此第一个类别的加权将是最重要的,第二个类别的加权会较小,等等。我当然想满足前两个条件,但是使该算法可扩展以满足N是非常理想的。最大化随机性(随机播放)不是优先事项。无论我在播放列表中的位置如何,我都想使听觉体验多样化。
这似乎与描述并解决了here的问题很接近,但是当所有项目都在具有多个尺寸的同一列表中,而不是不同大小的单独列表中时,我无法全神贯注于如何应用此问题。
这似乎是一个问题,目前已经解决了很多次,但我找不到任何示例。
最佳答案
这应该比蛮力要快得多:
您不会通过这种方式找到最佳选择,但是它应该能很快得出平庸的结果,并最终得到改善。
步骤2可以通过以下方式快速完成:(Ruby中的伪代码)
# Find the closest match to a song in slot_number
def closest_match(slot_number)
# Note: MAX can be less than N. Maybe nobody cares about songs more than 20 steps away.
(1..MAX).each |step|
return step if matches?(slot_number+step, slot_number) or matches?(slot_number-step, slot_number)
end
return MAX
end
# Given 2 slots, do the songs there match?
# Handles out-of-bounds
def matches?(x,y)
return false if y > N or y < 1
return false if x > N or x < 1
s1 = song_at(x)
s2 = song_at(y)
return true if s1.artist == s2.artist or s1.genre == s2.genere
return false
end
您也不必重新计算整个数组:如果缓存权重,则只要权重> = X的歌曲与交换的歌曲相差X步,就只需重新计算它们。例子:
| Song1 | Song2 | Song3 | Song4 | Song5 |
| Weight=3 | Weight=1 | Weight=5 | Weight=3 | Weight=2|
如果要交换歌曲2,则不必重新计算歌曲5:距离歌曲3 3步,但权重为2,因此不会“看到”歌曲3。
关于arrays - 沿多个类别(id3标签)均匀间隔列表项(播放列表歌曲)的算法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/31864897/