将列表分割为均衡长度的部分

Question

我需要一个算法，给定一个列表 L 和一个数字 N，它能返回一个包含 N 个小列表的列表，这些小列表要“平衡”。举个例子：

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

你可以看到，算法应该“优先”输出第一个列表。

我已经尝试了好几个小时，但就是想不出一个简洁好用的算法。顺便说一下，这个算法会用在Python中，但我现在主要想要的是算法本身。这不是作业，而是为了一个网站，网站会把内容以三列的形式展示（用Django框架）。

---

我在freenode的#python频道得到了最好的答案，内容如下：

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

不过别问我为什么它有效。:) 我会把正确答案给投票最多的那个人。

Answer 1

这是对喜欢函数式编程的人的致敬：

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)

这个稍微小一点：

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 2

假设你希望输出的列表在长度上尽量相等，如果不可能的话，就优先考虑前面的列表。子列表之间的长度差别不能超过一个。

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

这是我写的代码，没有进行排序。如果输入的数据没有排序的话，可以直接加上一个 lst.sort()。

我觉得这个代码写得不错，使用了迭代器，并且用 islice 来截取下一部分数据。

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