用于沿多个类别(id3标签)均匀地间隔列表项(播放列表歌曲)的算法

Question

我在设计算法以帮助创建mp3播放列表时遇到了麻烦,尽管可以根据我的用途调整列表中均匀分隔项目的更一般情况的算法.

一般情况是我想重新排序列表中的项目以最大化它们沿多个轴的多样性.

我的具体用例是我想将一堆歌曲转储到一个集合中,然后在集合上运行我的算法以生成一个有序的播放列表.我希望订单遵循这套标准:

1. 最大化同一艺术家的实例之间的距离
2. 最大化相同类型的实例之间的距离
3. 最大化X类实例之间的距离
4. N类别的等等

显然我们无法保证平等地优化所有类别,因此第一类加权最重要,第二加权更少,等等.我绝对想要满足前两个标准,但是使算法可扩展以满足N将是非常棒的.最大化随机性(shuffle)不是优先事项.无论我在播放列表中的哪个位置,我都希望将听觉体验多样化.

这似乎接近于此处描述和解决的问题,但是当所有项目都在具有多个维度的相同列表中而不是单独的不同大小的列表时,我无法解决如何应用此问题.

这似乎是一个本来可以解决很多次的问题,但我无法找到它的任何例子.

Answer 1

暴力算法很简单。

maxDistance = 0
foreach ordering
  distance = 0
  foreach category
    for i=1 to numsongs
      for j=i+1 to numsongs
        if song i and song j in this ordering have same value for this category
          distance = distance + (j-i)*weight_for_this_category
        endif
      endfor
    endfor
  endfor
  if ( distance > maxDistance )
    maxDistance = distance
    mark ordering as best one so far
  endif
endfor

但该算法的歌曲数量比指数复杂度更糟糕，因此它会花费相当快的难以管理的时间。困难的部分在于在合理的时间内完成它。