Splitting una lista en partes de longitudes equilibradas

Question

necesito un algoritmo que da una lista L y un número N, devuelve una lista de N listas más pequeñas, donde las sublistas son "equilibrada". Ejemplos:

algo(range(1, 8), 3) -> [[1,2,3], [4,5], [6,7]] 
algo(range(1, 6), 4) -> [[1,2], [3], [4], [5]] 
algo(range(1, 12), 5) -> [[1,2,3], [4,5], [6,7], [8,9], [10, 11]] 

Como puede ver, el algoritmo debe "preferir" la primera lista en la salida.

He estado intentando durante horas, pero no puedo encontrar un algoritmo bueno y concisa para ello. Esto se implementará en Python, por cierto, pero en realidad es el algoritmo que busco aquí. Esta es no deberes, esto es para un sitio web que mostrará los contenidos en una lista en tres columnas (Django).

---

Me dio la mejor respuesta entre #python en freenode y es de la siguiente manera:

def split_up(l, n): 
    q, r = divmod(len(l), n) 
    def division_point(i): 
     return i * q + min(i, r) 
    return [l[division_point(i):division_point(i+1)] for i in range(n)] 

No me preguntes por qué funciona sin embargo. :) Sin embargo, daré la respuesta correcta al que tenga más votos.

Answer 1

Este es el código que se me ocurrió, sin la clasificación. Solo toque una lst.sort() si la entrada no está ordenada.

Creo que esto salió muy bien, usando iteradores y utilizando islice para cortar la siguiente pieza.

import itertools 

def partlst(lst, n): 
    """Partition @lst in @n balanced parts, in given order""" 
    parts, rest = divmod(len(lst), n) 
    lstiter = iter(lst) 
    for j in xrange(n): 
     plen = len(lst)/n + (1 if rest > 0 else 0) 
     rest -= 1 
     yield list(itertools.islice(lstiter, plen)) 

parts = list(partlst(range(1, 15), 5)) 
print len(parts) 
print parts 

Answer 2

Si entiendo su problema ... sólo tendría que añadir un elemento para cada lista bajo mod (n), donde usted tiene algo (intervalo (a, b), n)

Por lo que debe :

1. tiene ba> n
2. Calcular BA = n * x + y (no sé realmente si existe el operador% en Python, lo que debería obtener y)
3. las primeras listas Y tendrán (ba/n + 1) elementos y las otras listas tendrán (ba/n)

Answer 3

Suponiendo que desea que la salida contenga listas de la misma longitud cuando sea posible, de lo contrario, dé preferencia a las listas al principio. Diferencia entre longitudes de sublistas no más de uno.

>>> l = [0, 1, 2, 3, 4, 5, 6] 
>>> def algo(li, n): 
     a, b = divmod(len(li), n) 
     c = [a + 1] * b + [a] * (n-b) 
     s = 0 
     for i, j in enumerate(c): 
      c[i] = li[s:s+j] 
      s += j 
     return c 

>>> algo(l, 3) 
[[0, 1, 2], [3, 4], [5, 6]] 
>>> algo(l, 4) 
[[0, 1], [2, 3], [4, 5], [6]] 

Answer 4

Aquí es un homenaje a los amantes funcionales:

def algo(l, n): 
    if n == 1: return [l] 
    q, r = divmod(len(l),n) 
    if r: q += 1 
    return [l[:q]] + algo(l[q:], n - 1) 

Ésta es un poco más pequeño:

def algo(l, n): 
    k = l[:] 
    q, r = divmod(len(l),n) 
    return [[k.pop(0) for _ in [0] * m] 
      for m in [q + 1] * r + [q] * (n - r)] 

Answer 5

poco tarde a la fiesta, pero ...

def algo(l, n): 
    return [l[-(-len(l)*i//n):-(-len(l)*(i+1)//n)] for i in range(n)] 

Use/en lugar de // en versiones anteriores de Python.