agrupando archivos en directorios de igual tamaño

Dada una lista ordenada de los nombres de archivo de la forma

{artist}-{title}.mp3 

Quiero distribuir los archivos en 255 bins (subdirectorios) para que cada bin contenga aproximadamente el mismo número de archivos, con la restricción de que los artistas son “atómicos”, es decir, que ningún artista debe tener pistas distribuidas en más de un directorio. El resultado debe permanecer ordenado también (es decir, ignorar el agrupamiento, todavía tenemos el mismo orden de la lista).

Lo que ya he intentado: particiono la lista en exactamente 255 partes mediante este método:

 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 

Y luego paso a través y hago cumplir la restricción de que los artistas son atómicos moviéndolos a la bandeja anterior si ya tienen otra pista allí. Este método es subóptimo y está roto, porque me quedan muchos contenedores vacíos (debido a que, en algunos casos, hay muchas pistas del mismo artista)

Después de hackearlo durante una hora, he aquí una solución mejor que se me ocurrió. Funciona creando un dict del artista a las pistas, y luego reduciéndolo a 255 teclas emparejando codiciosamente las entradas adyacentes cuando son pequeñas.

Estoy seguro de que aún no es óptimo, pero es viable y lo reproduciré aquí en caso de que alguien tenga un problema similar para resolver:

 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)