python - 根据字典中的键值对将字典列表拆分为具有列表长度的列表列表

Question

我有一个字典列表，按给定的键/值“权重”排序。例如，我想将它们组合在一起，以便权重永远不会超过 20，并且每个列表的长度不应超过 5，但每个字典组尽可能接近。输入看起来像这样:

[{'name': 'A', 'weight': 1}, 
 {'name': 'B', 'weight': 1}, 
 {'name': 'C', 'weight': 1}, 
 {'name': 'D', 'weight': 1}, 
 {'name': 'E', 'weight': 1},
 {'name': 'F', 'weight': 1}, 
 {'name': 'G', 'weight': 5}, 
 {'name': 'H', 'weight': 5}, 
 {'name': 'I', 'weight': 5}, 
 {'name': 'J', 'weight': 10}, 
 {'name': 'K', 'weight': 10}, 
 {'name': 'L', 'weight': 20},
 {'name': 'M', 'weight': 20},
]

输出应该是这样的:

[
 [
   {'name': 'A', 'weight': 1}, 
   {'name': 'B', 'weight': 1},
   {'name': 'C', 'weight': 1},
   {'name': 'D', 'weight': 1},
   {'name': 'E', 'weight': 1}
 ], 
 [
   {'name': 'F', 'weight': 1}, 
   {'name': 'G', 'weight': 5},
   {'name': 'H', 'weight': 5},
   {'name': 'I', 'weight': 5}
 ],
 [
   {'name': 'J', 'weight': 10}, 
   {'name': 'K', 'weight': 10}
 ],
 [
   {'name': 'L', 'weight': 20}
 ],
 [
   {'name': 'M', 'weight': 20}
 ]
]

另一个问题是我希望能够限制

的最大数量

我摆弄了一些列表理解，我有out = [dict_list[i:i + 5] for i in range(0, len(dict_list), 5)] 这允许我除以 5，但我无法弄清楚如何对列表进行加权。

Answer 1

您可以在 for 循环中继续将输入列表中的字典附加到输出列表的最后一个子列表，但如果输出列表为空，则创建一个新的子列表，最后一个子列表加上当前项的权重和超过 20，或者最后一个子列表的大小已经是 5。这在时间复杂度上只需要 O(n):

output = []
for item in lst:
    if not output or last_sum + item['weight'] > 20 or len(output[-1]) == 5:
        output.append([])
        last_sum = 0
    output[-1].append(item)
    last_sum += item['weight']

输出变成:

[[{'name': 'A', 'weight': 1},
  {'name': 'B', 'weight': 1},
  {'name': 'C', 'weight': 1},
  {'name': 'D', 'weight': 1},
  {'name': 'E', 'weight': 1}],
 [{'name': 'F', 'weight': 1},
  {'name': 'G', 'weight': 5},
  {'name': 'H', 'weight': 5},
  {'name': 'I', 'weight': 5}],
 [{'name': 'J', 'weight': 10},
  {'name': 'K', 'weight': 10}],
 [{'name': 'L', 'weight': 20}],
 [{'name': 'M', 'weight': 20}]]

演示:https://repl.it/@blhsing/ForcefulIroncladEmulation