CODEWITHSUNDEEP
pythonpython-3.x
xilopaint
xilopaint

Reputation: 745

Break list of integers into chunks respecting a maximum sum when possible

Let's say this is my list:

[5, 3, 13, 8, 1, 2, 6, 4, 10, 1, 12, 3, 7, 1, 4]

I want to break it into chunks respecting a maximum sum of 12 when possible so that the result should be like this:

[[5, 3], [13], [8, 1, 2], [6, 4], [10, 1], [12], [3, 7, 1], [4]]

Notice the code should not delete any integer greater than the maximum sum (in our case 13) but keep it isolated in a sublist.

I managed to do that with this code:

lst = [5, 3, 13, 8, 1, 2, 6, 4, 10, 1, 12, 3, 7, 1, 4]

start = 0
stop = 1
max_chunk_sum = 12
lst_count = len(lst)
result = []

while not stop > lst_count:
    chunk = lst[start:stop]
    chunk_sum = sum(chunk)
    chunk_count = len(chunk)

    if chunk_sum < max_chunk_sum:
        if stop != lst_count:
            stop += 1
        else:
            result.append(lst[start:stop])
            break
    else:
        if chunk_count == 1:
            result.append(lst[start:stop])
            start = stop
            stop += 1
        else:
            stop -= 1
            result.append(lst[start:stop])
            start = stop
            stop += 1

print(result)

Output:

[[5, 3], [13], [8, 1, 2], [6, 4], [10, 1], [12], [3, 7, 1], [4]]

But I feel there's a much smarter solution for this problem (maybe using list comprehension?).

Upvotes: 1

Views: 723

Answers (5)

godot
godot

Reputation: 1570

This is a typical work for reduce...

from functools import reduce
lst = [5, 3, 13, 8, 1, 2, 6, 4, 10, 1, 12, 3, 7, 1, 4]
init = lst[0:1]
rest = lst[1:]
max_sum = 12
reduce(lambda acc, cur: [*acc[0:-1], [*acc[-1], cur]]
                        if sum(acc[-1]) + cur <= max_sum else
                        [*acc, [cur]],
       rest,
       [init])

PS: it's also a pure function (immutable)...

Upvotes: 1

Alain T.
Alain T.

Reputation: 42133

You could use accumulate to compute the running sums with breaks on chunk overruns. Then use these sums to determine the ranges of indexes to include in each group:

a      = [5, 3, 13, 8, 1, 2, 6, 4, 10, 1, 12, 3, 7, 1, 4]
chunk  = 12

from itertools import accumulate
sums   = accumulate(a,lambda s,v: [s+v,v][s+v>chunk])
breaks = [ i+1 for (i,s),v in zip(enumerate(sums),a[1:]) if s+v>chunk]
groups = [ a[s:e] for s,e in zip([0]+breaks,breaks+[len(a)]) ]

print(groups)
# [[5, 3], [13], [8, 1, 2], [6, 4], [10, 1], [12], [3, 7, 1], [4]]

If you're looking for a solution without using libraries, here's a simple loop that will do it without using sum and without adding values multiple times :

array  = [5, 3, 13, 8, 1, 2, 6, 4, 10, 1, 12, 3, 7, 1, 4]
chunk  = 12

group,total = [],0
groups      = [group]
for value in array:
    total += value
    if total > chunk:
        group,total = [],value
        groups.append(group)
    group.append(value)

print(groups)

# [[5, 3], [13], [8, 1, 2], [6, 4], [10, 1], [12], [3, 7, 1], [4]]

Upvotes: 1

salt-die
salt-die

Reputation: 854

Similar to @phoenixo, but we can use a generator:

def cluster(iterable, max_int):
    start, *iterable = iterable
    cluster = [start]
    for value in iterable:
        if sum(cluster) + value <= max_int:
            cluster.append(value)
        else:
            yield cluster
            cluster = [value]
    yield cluster

Which gives us:

In [204]: list(cluster(ints, 12))
Out[204]: [[5, 3], [13], [8, 1, 2], [6, 4], [10, 1], [12], [3, 7, 1], [4]]

Upvotes: 1

Phoenixo
Phoenixo

Reputation: 2123

Here I iterate over lst, I use a sublist chunk, I check if this chunk would be > 12, otherwise I append the new element i in chunk. If it would be > 12, then I append the chunk to result, and I create a new chunk.

lst = [5, 3, 13, 8, 1, 2, 6, 4, 10, 1, 12, 3, 7, 1, 4]

max_chunk_sum = 12
result = []
chunk = []
for i in lst:
    if sum(chunk) + i <= max_chunk_sum:
        chunk.append(i)
    else:
        if chunk:
            result.append(chunk)
        chunk = [i]
result.append(chunk)
print(result)

Output :

[[5, 3], [13], [8, 1, 2], [6, 4], [10, 1], [12], [3, 7, 1], [4]]

Upvotes: 2

Sayse
Sayse

Reputation: 43320

You could use a list comprehension, but you could just check if the sum of adding the next element to the previous list would break the maximum value, if it does, append a new list.

result = [[lst.pop(0)]]

for item in lst:
    if sum(result[-1]) + item > max_chunk_sum:
        result.append([item])
    else:
        result[-1].append(item)

Upvotes: 4

Related Questions