1

您将如何平均分配每个都有值的子列表列表？

我想将以下列表分成 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
4

2 回答 2

3

这是一个简单的实现。首先，按权重对输入列表进行排序，然后枚举，将每个项目添加到最不满的桶中。

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]]
于 2014-04-23T22:28:47.860 回答
1

简洁地提出这个问题的一个起点是用组合学暴力破解它。为此，您可以使用 itertools。首先，您计算列表的所有 permutations()，然后使用 combination() 检查每个排列的所有可能组合，这可以为您提供每个排列的可能切片点。

然后您可以检查每个子列表（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]:]

当然，这取决于您的列表大小，这将需要一些时间，但它可以很容易地同时编程，例如通过让每个进程计算以某个数字开头的排列，但我将把如何做到这一点留给另一个问题。修剪也是可能的。

于 2014-04-24T07:46:48.053 回答