Разбить список словарей на список списков с длиной списка на основе пары ключ-значение внутри словаря - PullRequest
Новая
       20

Разбить список словарей на список списков с длиной списка на основе пары ключ-значение внутри словаря

2 голосов
/ 29 октября 2019

У меня есть список словарей, отсортированных по заданному ключу / значению «вес». Я хочу сгруппировать их, например, так, чтобы вес никогда не превышал 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, но у меня возникают проблемы с выяснением, как получить взвешенные списки.

1 Ответ

2 голосов
/ 29 октября 2019

Вы можете продолжать добавлять dict из списка ввода к последнему подсписку списка вывода в цикле 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']

output становится: 

[[{'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

...