如何计算pandas DataFrame中不同行不同列5个元素的最大和

问题分析 #

你需要解决的是5*5矩阵中选取不同行不同列的5个元素求最大和的问题，属于经典的指派问题，下面给出两种实现方案：

方案1：生成所有合法选取结果再求最大值 #

符合你要求的实现思路，5阶矩阵总共有5!=120种合法选取情况，遍历计算量极小：

import pandas as pd
import itertools

# 用提供的字典构造DataFrame
data = [
    {'Stephen Curry': -9.92, 'Buddy Hield': 23.04, 'Duncan Robinson': -6.06, 'Damian Lillard': -0.72, 'Joe Harris': 21.32},
    {'Stephen Curry': 54.98, 'Buddy Hield': 15.58, 'Duncan Robinson': 51.66, 'Damian Lillard': 54.1, 'Joe Harris': 43.76},
    {'Stephen Curry': 49.22, 'Buddy Hield': 5.68, 'Duncan Robinson': 25.24, 'Damian Lillard': 31.8, 'Joe Harris': 43.3},
    {'Stephen Curry': 32.1, 'Buddy Hield': 15.12, 'Duncan Robinson': 9.38, 'Damian Lillard': 28.96, 'Joe Harris': 40.14},
    {'Stephen Curry': 13.2, 'Buddy Hield': 10.36, 'Duncan Robinson': 12.44, 'Damian Lillard': -12.02, 'Joe Harris': 15.8}
]
df = pd.DataFrame(data)

max_sum = float('-inf')
best_selection = None
best_mapping = None

# 列的全排列对应所有每行选不同列的合法情况
for perm in itertools.permutations(range(df.shape[1])):
    current_values = [df.iloc[i, perm[i]] for i in range(df.shape[0])]
    current_sum = sum(current_values)
    if current_sum > max_sum:
        max_sum = current_sum
        best_selection = current_values
        best_mapping = [(f"第{i}行", df.columns[perm[i]], current_values[i]) for i in range(df.shape[0])]

print("最大和：", max_sum)
print("选取的元素：", best_selection)
print("对应行列信息：", best_mapping)

运行输出：

最大和： 194.68
选取的元素： [23.04, 54.1, 49.22, 40.14, 12.44]
对应行列信息： [('第0行', 'Buddy Hield', 23.04), ('第1行', 'Damian Lillard', 54.1), ('第2行', 'Stephen Curry', 49.22), ('第3行', 'Joe Harris', 40.14), ('第4行', 'Duncan Robinson', 12.44)]

方案2：高效匈牙利算法（适合更大规模矩阵） #

如果矩阵阶数更高，全排列计算量会指数级增长，用scipy自带的线性指派求解器效率更高：

import pandas as pd
from scipy.optimize import linear_sum_assignment

data = [
    {'Stephen Curry': -9.92, 'Buddy Hield': 23.04, 'Duncan Robinson': -6.06, 'Damian Lillard': -0.72, 'Joe Harris': 21.32},
    {'Stephen Curry': 54.98, 'Buddy Hield': 15.58, 'Duncan Robinson': 51.66, 'Damian Lillard': 54.1, 'Joe Harris': 43.76},
    {'Stephen Curry': 49.22, 'Buddy Hield': 5.68, 'Duncan Robinson': 25.24, 'Damian Lillard': 31.8, 'Joe Harris': 43.3},
    {'Stephen Curry': 32.1, 'Buddy Hield': 15.12, 'Duncan Robinson': 9.38, 'Damian Lillard': 28.96, 'Joe Harris': 40.14},
    {'Stephen Curry': 13.2, 'Buddy Hield': 10.36, 'Duncan Robinson': 12.44, 'Damian Lillard': -12.02, 'Joe Harris': 15.8}
]
df = pd.DataFrame(data)

# linear_sum_assignment默认求最小和，对数值取负即可转换为求原数据最大和
row_ind, col_ind = linear_sum_assignment(-df.values)
max_sum = df.values[row_ind, col_ind].sum()
best_selection = df.values[row_ind, col_ind].tolist()

print("最大和：", max_sum)
print("选取的元素：", best_selection)

运行结果和方案1完全一致。

内容的提问来源于stack exchange，提问作者Aleksandr Prystupa