Break a dictionary keys into a list of lists not exceeding sum

sierra_papa 0
Viewed 33

Lets say I have the following dictionary:

d = {'key1': 3, 'key2': 7, 'key3': 8, 'key4': 10, 'key5': 15, 'key6': 22}

How do I convert it to a list of lists consisting of keys, where the sum of dictionary values corresponding to each sublist's keys does not exceed 20 unless a single value is greater than 20 (d['key6'] here)? So the expected result in this case would be:

list_of_dict = [['key1', 'key2', 'key3'], ['key4'], ['key5'], ['key6']]

or

list_of_dict = [['key1', 'key2'], ['key3', 'key4'], ['key5'], ['key6']]

The order is not important and there should be as few sublists as possible (i.e [['key1'], ['key2'], ['key3'], ['key4'], ['key5'], ['key6']] is not acceptable).

dictionary python
2 Answers

I generally agree with @Olvin Right 's strategy of maintaining a counter while compiling a list to return. However since you need as few sublists as possible in the result, I'd recommend using a list of counters (with values corresponding to the return list) so that you can add keys 'later' in the dict to early entries in the list.

For when this approach would be useful, consider this dict:

d = {'key1': 18, 'key2': 19, 'key3': 2}
bjdev0

I ended up with the following function based on Olvin Roght's comment. If somebody has a cleaner/more efficient solution, I will be happy to accept it.

def break_keys(d, max_sum):
    d = {k: v for k, v in sorted(d.items(), key=lambda item: item[1])}
    current_keys = []
    result = []
    current_sum = 0
    for k, v in d.items():
        current_sum += v
        if current_sum > max_sum:
            # do not append empty list if the first value is greater than max_sum value
            if current_keys:
                result.append(current_keys)
                current_keys = [k]
                current_sum = v
            else:
                result.append([k])
        else:
            current_keys.append(k)
    if current_keys:
        result.append(current_keys)
    return result
sierra_papa0
Related