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.

You have to sort beforehand if I'm thinking right. What is wrong with lst.sort(), then traaversing it linearly to pick off elements? It is O([the sort func]) anyway. — u0b34a0f6ae, Sep 04 '09 at 16:11
http://stackoverflow.com/questions/320170/how-do-i-divide-an-ordered-list-of-integers-into-evenly-sized-sublists — Corey D, Sep 04 '09 at 16:17
@voyager: Adapting that algorithm to this problem in Python is a trivial exercise. — Corey D, Sep 04 '09 at 16:25
What do you mean by balanced? If you're trying to minimize the maximum sum of any sub-list, there's a an app ---- I mean, a solution for that. Will dig it up in case if such is the case. — agorenst, Sep 04 '09 at 16:33
very nice solution you posted. the division_point thing is really neat. Just like my solution (in a way) it takes 1 from the rest ("r") until it is used up (i = 0, 1, 2, 3.. then i > r, min(i, r) == r). — u0b34a0f6ae, Sep 04 '09 at 18:17

score 5 · Accepted Answer · edited Sep 04 '09 at 17:57

5

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

edited Sep 04 '09 at 17:57

Crescent Fresh

115,249
25
154
140

answered Sep 04 '09 at 16:21

u0b34a0f6ae

48,117
14
92
101

This is a bout as terse as it gets. It is a sort of tricky problem though. – Justin Sep 04 '09 at 17:13
it'd be an interesting code golf problem. I'm still tinkering with a solution. – Kenan Banks Sep 04 '09 at 17:54

SilentGhost · Answer 2 · 2009-09-04T17:41:24.173

Assuming you want output to contain lists of equal length when possible, otherwise give preference to lists in the beginning. Difference between lengths of sub-lists no more than one.

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

score 0 · Answer 3 · answered Sep 04 '09 at 16:16

If I understand your problem... you would only have to add one item for each list under mod(n), where you have algo (range(a,b), n)

So you should:

Have b-a > n
Calculate b-a = n*x + y (I dont really know if the operator % exists on python, so you should get y)
The first y lists will have (b-a/n + 1) elements and the other lists will have (b-a/n)

score 0 · Answer 4 · answered Sep 04 '09 at 19:44

Here's a tribute to functional lovers:

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)

This one is a little bit smaller:

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

score 0 · Answer 5 · answered Nov 04 '09 at 14:51

0

Bit late to the party, but...

def algo(l, n):
  return [l[-(-len(l)*i//n):-(-len(l)*(i+1)//n)] for i in range(n)]

Use / instead of // in older versions of Python.

answered Nov 04 '09 at 14:51

Alice Purcell

12,622
6
51
57

I haven't tested it, but if it works, then I'll be damned! :) – Deniz Dogan Nov 04 '09 at 19:52
Those double negatives seem to be useless. I redefined it as: `[lst[len(lst) * i // n : len(lst) * (i + 1) // n] for i in range(n)]`. – Mahyar Mirrashed Jun 15 '22 at 07:46
1

@MahyarMirrashed Removing the double-negatives means the algorithm puts more items in later lists rather than earlier ones, which the OP did not want. Try it with e.g. algo([1,2,3,4], 3) to see the difference – Alice Purcell Jun 16 '22 at 11:24

Splitting up a list into parts of balanced lengths

5 Answers5