将“加权”列表/数组分割为相等大小的块

Question

我有一个项目数组，每个项目都有一个权重。我想把它分成大小相等，累积重量相等的块。这里有一个答案可以使用numpyhttps://stackoverflow.com/a/33555976/10690958 有没有一种简单的方法可以使用纯python来实现这一点？在

示例数组：

[ ['bob',12],
 ['jack,6],
 ['jim',33],
....
]

或者

^{pr2}$

这里正确的输出是（假设需要2个块）

 [a,11],[b,2] - cumulative weight of 13

以及

[c,5],[d,3],[e,3],[f,2] - cumulative weight of 13

为了进一步澄清这个问题，设想一个将100人分为10部电梯的情况，我们希望每部电梯具有相同的近似总重量（该电梯中所有人的重量总和）。因此，第一个列表将成为名称和权重。这是一个负载平衡问题。在

Answer 1

您只需模仿cumsum：构建一个对权重求和的列表。最后你得到了总重量。用累积的权重扫描列表，并在每次达到“块的总重量/数量”时创建一个新的块。代码可以是：

 def split(w_list, n_chunks):
    # mimic a cumsum
    s = [0,[]]
    for i in w_list:
        s[0]+= i[1]
        s[1].append(s[0])
    # now scan the lists populating the chunks
    index = 0
    splitted = []
    stop = 0
    chunk = 1
    stop = s[0] / n_chunks
    for i in range(len(w_list)):
        # print(stop, s[1][i])     # uncomment for traces
        if s[1][i] >= stop:        # reached a stop ?
            splitted.append(w_list[index:i+1])    # register a new chunk
            index = i+1
            chunk += 1
            if chunk == n_chunks:                 # ok we can stop
                break
            stop = s[0] * chunk / n_chunks        # next stop
    splitted.append(w_list[index:])               # do not forget last chunk
    return splitted

Answer 2

你需要这样的分割：

 array =[ ['bob',12],
 ['jack',6],
 ['jim',33],
  ['bob2',1],
 ['jack2',16],
 ['jim2',3],
  ['bob3',7],
 ['jack3',6],
 ['jim3',1],
 ]


array = sorted(array, key= lambda pair: pair[1],  )

summ = sum(pair[1] for pair in array )

chunks = 4

splmitt = summ // chunks

print(array)

print(summ)

print(splmitt)

def split(array, split):

    splarr = []
    tlist = []
    summ = 0

    for pair in array:
        summ += pair[1] 
        tlist.append(pair)     
        if summ > split:
            splarr.append(tlist)
            tlist = []
            summ = 0


if tlist:
    splarr.append(tlist)
return splarr

spl = split(array, splmitt)

import pprint 

pprint.pprint(spl)