How would you evenly distribute a list of sublists that each have a numerical value across three lists?

Question

How would you evenly distribute a list of sublists that each have a value?

I'd like to distribute the following list into 3 lists.

lst = [['a',10],['b',40],['c',10],['d',30],['e',20],['f',100],['g',90],['h',4]]

Since the aggregate of all the values is 304, the three lists should aggregate to about 101.3.

This is the result I'd like to produce in some form.

lst1 = [['g',90],['a',10]]
lst2 = [['f',100],['h',4]]
lst3 = [['b',40],['c',10],['d',30],['e',20]]

This is the solution I have so far that addresses it but needs some work to make it faster.

def ListSum(lst):
    lst = map(lambda subli: subli[1],lst)
    return sum(lst)

def EvenlyDistribute(lst):
    #put into bucket until reached, then move to the next bucket
    Lst1 = []
    Lst2 = []
    Lst3 = []
    for subli in lst:
        try:
            if ListSum(Lst1) < 100:
                Lst1.append(subli)
            elif ListSum(Lst2) < 100:
                Lst2.append(subli)
            else:
                Lst3.append(subli)
        except:
            pass
    print Lst1
    print Lst2
    print Lst3

Answer 1

Here's a simple implementation. First, sort the input list by weight, then enumerate, adding each item to the least full bucket.

def EvenlyDistribute(lst, n):
    """Distribute items in lst (tuples of (val, weight)) into n buckets"""
    buckets = [[] for i in range(n)]
    weights = [[0, i] for i in range(n)]
    for item in sorted(lst, key=lambda x: x[1], reverse=True):
        idx = weights[0][1]
        buckets[idx].append(item)
        weights[0][0] += item[1]
        weights = sorted(weights)
    return buckets

so

for i, v in enumerate(EvenlyDistribute(lst, 3)):
    print(v)

returns

[['f', 100], ['h', 4]]
[['g', 90], ['a', 10]]
[['b', 40], ['d', 30], ['e', 20], ['c', 10]]

Answer 2

A starting point present this problem compactly is to brute-force it with combinatorics. For this you could use itertools. First you compute all permutations() of your list, then you check all possible combinations of each permutation with combinations() that can give you the possible slice points for each permutation.

Then you can check the variance of the sums of each of these sublists (sl0-2) as shown in other answers. Then retain the one with the lowest variance and return that at the end of the process.

from itertools import permutations, combinations

for perm in permutations(grades):
    for i in combinations(xrange( len(grades)), 3):
        sl0, sl1, sl2 =  perm[i[0]:i[1]], perm[i[1]:i[2]],  perm[i[2]:]

Depending on your list size this will take some time, of course, but it can easily be programmed concurrently, e.g by letting each process calculate permutations that starts with a a certain number(s), but I'll leave how to do that for another question. Pruning is also possible.