'Balanced' groups

balanced-groups.py

#!/usr/bin/env python

def balanced_groups(ngroups, items):
    items = sorted(items)
    wgroups = [0] * ngroups
    groups = [[] for _ in xrange(ngroups)]

    g = 0
    lo = 0
    dir = 1
    hi = len(items) - 1
    maxv = items[hi]
    total = sum(items)
    while hi >= lo:
        # add the hi one
        total -= items[hi]
        wgroups[g] += items[hi]
        groups[g].append(items[hi])
        hi -= 1

        # fill with low
        while lo < hi and wgroups[g] < maxv:
            total -= items[lo]
            wgroups[g] += items[lo]
            groups[g].append(items[lo])
            lo += 1
        maxv = wgroups[g]

        g += dir
        if g == ngroups:
            dir = -1
            g = ngroups - 1
        elif g < 0:
            dir = 1
            g = 0

    assert total == 0, total
    return groups

def human_size(size):
    if size >= (1 << 40): return '%.2fTiB' % (size / 1099511627776.0)
    if size >= (1 << 30): return '%.2fGiB' % (size / 1073741824.0)
    if size >= (1 << 20): return '%.2fMiB' % (size / 1048576.0)
    if size >= (1 << 10): return '%.2fKiB' % (size / 1024.0)
    return size


if __name__ == '__main__':
    from random import randint

    def test(func, data):
        print '\n', func
        maxdiff = None
        prev = None
        for g in func(3, data):
            print 'total-size: %s items: %d' % (human_size(sum(g)), len(g))
            if prev is not None:
                maxdiff = max(maxdiff, abs(sum(g) - prev))
            prev = sum(g)
        print 'maxdiff %s' % (human_size(maxdiff))
        return maxdiff

    for _ in xrange(5):
        data = [randint(1024 * 1024, 2 * 1024 * 1024 * 1024) for _ in xrange(10000)]
        test(balanced_groups, data)