2

给定表单文件名的排序列表

{artist}-{title}.mp3

我想将文件分发到 255 个 bin（子目录）中，以便每个 bin 包含大约相等数量的文件，并限制艺术家是“原子的”，即没有艺术家应该将曲目分布在一个以上的目录中。结果也应该保持排序（即忽略分箱，我们仍然有相同的列表排序）。

我已经尝试过：我通过这种方法将列表分成 255 个部分：

def partition(lst, n):
    q, r = divmod(len(lst), n)
    indices = [q * i + min(i, r) for i in range(n + 1)]
    result = [lst[indices[i]:indices[i + 1]] for i in range(n)]
    assert sum(len(x) for x in result) == len(lst)
    assert len(set(len(x) for x in result)) <= 2
    return result

然后，如果他们已经有另一首曲目，我会通过将艺术家移到前一个 bin 中来执行并强制执行艺术家是原子的限制。这种方法是次优且损坏的，因为我留下了很多空箱（由于在某些情况下，同一艺术家的许多曲目）

4

1 回答 1

1

在破解了一个小时后，这是我想出的更好的解决方案。它的工作原理是为曲目创建一个dict艺术家，然后通过贪婪地配对较小的相邻条目来将其缩减到 255 个键。

我确信它仍然不是最佳的，但它是可行的，我会在这里重现它，以防有人有类似的问题需要解决：

d = collections.OrderedDict()
# build an OrderedDict of artist to track(s)
for fn in files:
    artist, title = fn.split('-')
    if (artist,) not in d:
        d[artist,] = []
    d[artist,].append(fn)

def window(seq, n=2):
    it = iter(seq)
    result = tuple(itertools.islice(it, n))
    if len(result) == n:
        yield result    
    for elem in it:
        result = result[1:] + (elem,)
        yield result

while len(d) > 255:
    # find the pair of adjacent keys with minimal number of files contained
    k1, k2 = min(window(d), key=lambda x: len(d[x[0]] + d[x[1]]))
    # join them into the first key and nuke the latter
    d[k1] += d.pop(k2)
于 2013-04-15T15:27:20.907 回答