CODEWITHSUNDEEP
pythonpython-2.7dictionarylist-comprehension
Cdhippen
Cdhippen

Reputation: 655

Split list of dictionaries into list of lists with list length based on a key value pair inside the dictionary

I have a list of dictionaries, sorted by a given key/value 'weight'. I want to group these together for example so that weight never exceeds 20, and each list shouldn't exceed a length of 5, but gets as close as possible per dict group. The input would look like this:

[{'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},
]

And the output should look like this:

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

Another catch is that I'd like to be able to limit the max number of

I fiddled around with some list comprehension, and I have out = [dict_list[i:i + 5] for i in range(0, len(dict_list), 5)] which allows me to split by 5, but I'm having trouble figuring out how to get the lists weighted.

Upvotes: 2

Views: 214

Answers (1)

blhsing
blhsing

Reputation: 106455

You can keep appending the dict in the input list to the last sub-list of the output list in a for loop, but create a new sub-list if the output list is empty, the weight sum of the last sub-list plus the current item exceeds 20, or the size of the last sub-list is already 5. This would cost only O(n) in time complexity:

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 becomes:

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

Demo: https://repl.it/@blhsing/ForcefulIroncladEmulation

Upvotes: 4

Related Questions