Splitting up a list into parts of balanced lengths

Question

Hi

I need an algorithm which given a list L and a number N, returns a list of N smaller lists where the sublists are "balanced". Examples:

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]]

As you can see, the algorithm should "prefer" the first list in the output.

I've been trying for hours, but I can't figure out a nice and terse algorithm for it. This will be implemented in Python, by the way, but it's really the algorithm that I'm after here. This is not homework, this is for a website which will display contents in a list in three columns (Django).

---

I got the best answer from #python on freenode and it is as follows:

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)]

Don't ask me why it works though. :) I'll give the correct answer to the one with most votes though.

Answer 1

If I understand your problem... you would only have to add one item for each list under mod(n), where you have algo (range(a,b), n)

So you should:

1. Have b-a > n
2. Calculate b-a = n*x + y (I dont really know if the operator % exists on python, so you should get y)
3. The first y lists will have (b-a/n + 1) elements and the other lists will have (b-a/n)

Answer 2

This is the code I came up with, without the sorting. Just slap on a lst.sort() if the input is not sorted.

I think this came out nicely, using iterators and using islice to cut off the next piece.

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 3

Assuming you want output to contain lists of equal length when possible, otherwise give preference to lists in the beginning. Difference between lengths of sub-lists no more than one.

>>> 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

Here's a tribute to functional lovers:

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)

This one is a little bit smaller:

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

Bit late to the party, but...

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

Use / instead of // in older versions of Python.