How to Chunk list of numbers so that sum of each chunk less than n?

Question

I've tried searching for a solution to this, but my ignorance of precise terminology doesn't help, hopefully the title of the question and the code below is enough explanation.

Here's my working so far:

C = [1,1,1,1,2,3,1,1,1,2,1]
sub_C = []
chunked_C = []
counter = 0
for i in C:
    counter += i
    if counter <= 3:
        sub_C.append(i)
    else:
        chunked_C.append(list(sub_C))
        del sub_C[:]
        counter = i
        sub_C.append(i)
print chunked_C

I want chunked_C to produce: [[1,1,1],[1,2],[3],[1,1,1],[2,1]]

Not sure where I'm going wrong, perhaps someone can help.

Edit: I've corrected the typos.

Also:

A slight revision in that I would need the incomplete tail of the list to be chunked too i.e. where the value is less than 3 but I run out of numbers.

e.g:

C = [1,1,1,1,2,3,1,1,1,2,1,1]
so chunked_C = [[1,1,1],[1,2],[3],[1,1,1],[2,1],[1]]

Hope that makes sense.

A further revision:

if C = [1,1,1,1,1,2,3,1,1,1,2,1]

chunked_C would equal [[1,1,1],[1,1],[2],[3],[1,1,1],[2,1]]

So I guess the logic needs to be revised further.

Answer 1

Edit: Firstly, a correction as Ashwini Points out in the comments, we need to be sure we release the last chunk, even if it doesn't hit the target.

That said, there is a better solution to this problem using itertools.groupby():

import itertools

c = [1,1,1,1,2,3,1,1,1,2,1]

class group_by_sum:
    def __init__(self, target):
        self.target = 3
        self.current = False
        self.sum = 0

    def __call__(self, item):
        self.sum += item
        if self.sum > self.target:
            self.sum = item
            self.current = not self.current
        return self.current

    def group(self, iterable):
        return [tuple(items) for _, items in itertools.groupby(iterable, self)]

>>> group_by_sum(3).group(c)

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

Obviously, the convenience method at the end isn't necessarily important, but it makes it simpler to use.

---

Old Answer:

This can be done nicely with a generator:

def chunk_to_sum(iterable, target):
    chunk_sum = 0
    chunk = []
    for item in iterable:
        chunk_sum += item
        if chunk_sum > target:
            yield chunk
            chunk = [item]
            chunk_sum = item
        else:
            chunk.append(item)
    if chunk: yield chunk

>>> list(chunk_to_sum([1, 1, 1, 1, 2, 3, 1, 1, 1, 2, 1], 3))
[[1, 1, 1], [1, 2], [3], [1, 1, 1], [2, 1]]

Answer 2

I think the line "if counter < 3:" is backwards logic from what you want it to be. Here's a corrected version I wrote up:

def chunk(to_chunk, n):
    """ 
    >>> chunk([1,1,1,1,2,3,1,1,1,2,1], 3) 
    [[1, 1, 1], [1, 2], [3], [1, 1, 1], [2, 1]]
    """

    result, accum, total = [], [], 0

    for i in to_chunk:
        accum.append(i)

        if total + i >= n:
            result.append(accum)
            accum, total = [], 0
        else:
            total += i

    return result