给定格式为文件名的排序列表
{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
然后我通过将艺术家移动到上一个容器中(如果他们已经在那里有另一个轨道)来强制执行艺术家是原子的限制。这种方法是次优的并且有问题，因为我留下了很多空箱(由于在某些情况下，同一艺术家的许多轨道)
请您参考如下方法:
在苦苦思索了一个小时之后，我想到了一个更好的解决方案。它的工作原理是创建艺术家的 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)
