Splitting up a list into parts of balanced lengths

Question

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

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