如何将具有数值的子列表均匀分配到三个列表中？

Question

如何将一个包含子列表的列表均匀分配，每个子列表都有一个值？

我想把下面这个列表分成3个列表。

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

因为所有值的总和是304，所以这三个列表的总和应该大约是101.3。

这是我想要得到的结果，某种形式的。

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

这是我目前为止找到的解决方案，但还需要一些改进，以便让它运行得更快。

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

解决这个问题的一个简单方法是用暴力法结合组合数学。你可以使用一个叫做 itertools 的工具。首先，你需要计算出列表的所有排列组合，然后再检查每个排列的所有可能组合，这样就能找到每个排列的切分点。

接着，你可以检查这些子列表（比如 sl0-2）中每个子列表的和的方差，具体方法在其他回答中有提到。最后，保留方差最小的那个子列表，并在整个过程结束时返回它。

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

当然，根据你的列表大小，这个过程可能需要一些时间，不过你可以通过并行处理来加快速度，比如让每个进程计算以某个数字开头的排列组合。不过，如何实现这个就留给另一个问题来讨论了。另外，剪枝也是一种可行的方法。

Answer 2

这里有一个简单的实现方法。首先，把输入的列表按照重量进行排序，然后逐个处理，把每个物品放到最不满的桶里。

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

所以

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

返回

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