1

それぞれが値を持つサブリストのリストをどのように均等に配布しますか?

次のリストを 3 つのリストに分けて配布したいと思います。

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

すべての値の合計は 304 なので、3 つのリストを合計すると約 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() を計算し、次に、各順列の可能なスライス ポイントを得るために、combinations() を使用して、各順列のすべての可能な組み合わせをチェックします。

次に、他の回答に示されているように、これらの各サブリスト (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 に答える