Python 按阈值将词典拆分为更小的词典

Question

给定以下字典：

dict_sports = {'Skateboarding': 163,
 'Bowling': 134,
 'Rugby': 83,
 'Wrestling': 57,
 'Baseball': 30,
 'Badminton': 24,
 'Volleyball': 22,
 'Basketball': 18,
 'Football': 16,
 'Weightlifting': 15,
 'Golf': 14,
 'Skiing': 10,
 'Boxing': 8,
 'Cricket': 6}

total_sum = sum([v for k,v in dict_sports.items()])

print(total_sum)

我想将词典拆分成3个较小的词典；从而满足以下条件：

三个词典各自值的总和；应该接近某个阈值；说一个百分比 plus/minus %2.5 of 200.

即每个字典值的总和应为：

195 <= total_sum <= 205

这是我的解决方案，解决了我原来的问题，但仍然与我上面提出的条件相矛盾，这可能是因为数据本身（不能以这种精度拆分)... 我的问题不在于拆分的 accuracy；我的问题是 编码量 我必须完成这个简单的任务！

list_01 = []
list_02 = []
list_03 = []

dict_01 = {}
dict_02 = {}
dict_03 = {}

for k,v in dict_sports.items():
    if  (sum(list_01) < 195) and (k not in dict_02) and (k not in dict_03):
        list_01.append(v)
        dict_01[k] = v
        if sum(list_01) > 205:
            list_01.pop()
            dict_01.pop(k, None)
            
print(sum(list_01))            

for k,v in dict_sports.items():
    if  (sum(list_02) < 195) and (k not in dict_01) and (k not in dict_03):
        list_02.append(v)
        dict_02[k] = v
        if sum(list_02) > 205:
            list_02.pop()
            dict_02.pop(k, None)
            
print(sum(list_02))            
            
for k,v in dict_sports.items():
    if  (sum(list_03) < 195) and (k not in dict_01) and (k not in dict_02):
        list_03.append(v)
        dict_03[k] = v
        if sum(list_03) > 205:
            list_03.pop()
            dict_03.pop(k, None)

print(sum(list_03))

print(dict_01)
print(dict_02)
print(dict_03)

我想有更好的方法来解决这个问题，也许是 pandas，或者任何其他 python 库或第三方库；或者比这更好的代码！

Answer 1

首先，您在这里描述的内容非常接近（或者是？）Multiple knapsack problem。有很多方法可以解决这个问题，具体取决于您对结果施加的条件。

我建议您阅读此页面以及与之相关的资源，以便更好地构建您想要的输出。例如，我们可以省略 items 吗？如果我们不能用当前的项目列表满足您对结果的限制（在 [195,205] 内）怎么办？

使用纯 python，使用贪婪方法减少代码量的天真方法可能是（假设您的字典按降序排序）：

# Initialize a list of dictionaries to fill
dicts = [{},{},{}]
# Define a counter
i = 0
# Define your maximum value
max_value = 205


for k,v in dict_sports.items():
    for i in range(len(dicts)):
        if sum(dicts[i].values()) + v < max_value:
            dicts[i].update({k:v})
            break
    i+=1

for d in dicts:
    print("---- {} ----".format(sum(d.values())))
    print(d)

给予

---- 203 ----
{'Skateboarding': 163, 'Baseball': 30, 'Skiing': 10}
---- 199 ----
{'Bowling': 134, 'Wrestling': 57, 'Boxing': 8}
---- 198 ----
{'Rugby': 83, 'Badminton': 24, 'Volleyball': 22, 'Basketball': 18, 'Football': 16, 'Weightlifting': 15, 'Golf': 14, 'Cricket': 6}

请注意，如果不满足所有字典的求和条件，此解决方案可能会跳过项目。

Answer 2

仔细观察，三个for循环的主体仅在变量名上有所不同。否则他们实现相同的算法。这种代码重复可以通过将算法抽象成一个函数而不是重复三次来消除。

与其仅仅显示最终结果，我认为勾勒出实现目标的可能过程会更有用。

让我们先简单地将重复的代码包装在一个函数中：

list_01 = []
list_02 = []
list_03 = []

dict_01 = {}
dict_02 = {}
dict_03 = {}

def split_dict():
    for k, v in dict_sports.items():
        if  (sum(list_01) < 195) and (k not in dict_02) and (k not in dict_03):
            list_01.append(v)
            dict_01[k] = v
            if sum(list_01) > 205:
                list_01.pop()
                dict_01.pop(k, None)

split_dict()
            
print(sum(list_01))    
#...

现在我们不希望我们的函数修改全局变量但是 return 计算结果：

def split_dict():
    list_01 = []
    dict_01 = {}
    for k, v in dict_sports.items():
        if  (sum(list_01) < 195) and (k not in dict_02) and (k not in dict_03):
            list_01.append(v)
            dict_01[k] = v
            if sum(list_01) > 205:
                list_01.pop()
                dict_01.pop(k, None)
    return list_01, dict_01

list_01, dict_01 = split_dict()

如果要重用函数，我们需要改变if条件中的dict_02和dict_03，所以我们把它们变成参数：

def split_dict(dict_02, dict_03):
    # ... unchanged code omitted for brevity
    return list_01, dict_01

list_01, dict_01 = split_dict(dict_02, dict_03)

在本地和全局使用相同的变量名是不好的做法，而且函数应该在不同的情况下工作。因此，让我们清理并使用更通用和描述性的名称：

def split_dict(exclude_01, exclude_02):
    selected_values = []
    selected_items = {}
    for k, v in dict_sports.items():
        if  (sum(selected_values) < 195) and (k not in exclude_01) and (k not in exclude_02):
            selected_values.append(v)
            selected_items[k] = v
            if sum(selected_values) > 205:
                selected_values.pop()
                selected_items.pop(k, None)
    return selected_values, selected_items

list_01, dict_01 = split_dict(dict_02, dict_03)

最后，只需使用不同的输入和输出变量，我们就可以在所有三个地方使用该函数：

list_01, dict_01 = split_dict({}, {})            
print(sum(list_01))            
            
list_02, dict_02 = split_dict(dict_01, {})            
print(sum(list_02))            

list_03, dict_03 = split_dict(dict_01, dict_02)    
print(sum(list_03))

此时，代码量减少了接近 3 倍。它还有一个好处，如果你想进一步调整算法，只需更改一个地方。

关于后续步骤的一些建议：

尝试将 exclude_01 和 exclude_02 组合成一个函数参数
将硬编码数字常量更改为函数参数
通过先检查总和来避免后续 append/pop
提出一种新算法，即使在以后的拆分中也能满足约束条件
...

Python 按阈值将词典拆分为更小的词典

Python Split Dictionary into Smaller Dictionaries by Threshold Value

python

math

dictionary

python-3.x

pandas