python - 按项目总和分组列表

Question

我正在寻找一种将整数列表分组到列表列表中的有效方法，其中原始项目的总和不超过给定数字。

请考虑以下整数列表：

[1, 1, 1, 1, 2, 2, 1, 3, 1, 1, 2]

应将其分组，以使项目的总和不超过 3：

[[1, 1, 1], [1, 2], [2, 1], [3], [1, 1], [2]]

Answer 1

def group(lst, limit):

    lim = 0
    grp = []

    for x in lst:
        if x + lim > limit:
            yield grp
            grp = []
            lim = 0

        grp.append(x)
        lim += x

    yield grp

print list(group([1, 1, 1, 1, 2, 2, 1, 3, 1, 1, 2], 3))

Answer 2

使用itertools.groupby：

import itertools

def sumkey(n):
    sc = [0, 0] # sum, count => group by
    def keyfunc(x):
        sc[0] += x
        if sc[0] > n:
            sc[1] += 1
            sc[0] = x
        return sc[1]
    return keyfunc

xs = [1, 1, 1, 1, 2, 2, 1, 3, 1, 1, 2]
print([list(grp) for _, grp in itertools.groupby(xs, key=sumkey(3))])

在 Python 3 中，sumkey可以使用以下方式编写nonlocal：

def sumkey(n):
    sum_, count = 0, 0
    def keyfunc(x):
        nonlocal sum_, count
        sum_ += x
        if sum_ > n:
            count += 1
            sum_ = x
        return count
    return keyfunc

Answer 3

不是最聪明的解决方案，但足够干净和简单：

def makeList(inList, n):
    aList = []
    while len(inList) > 0 and sum(aList) + inList[0] <= n :
        aList.append(inList.pop(0))

    return aList

def groupLists(inList, n, outList = []):
    if not n:
        raise ValueError("Please enter a positive integer")     
    while len(inList):
        outList.append(makeList(inList, n))
    return outList

print groupLists([1,1,1,1,2,2,1,3,1,1,2], 3)