python - 找到矩阵中的最大值以最大化分数

Question

问题:

我想在每个老师和每个小组的矩阵中找到最高值，以最大化哪个小组应该与哪个老师一起去的比例。

            Teacher A   Teacher B   Teacher C   Teacher D
Group 1     50          40          20           50
Group 2     30          10          40          100
Group 3     80          60          40           20

在上表中。我知道如何找出行和列中的最高值，但我想在教师和组的组合中找到最高值，即教师不能属于两个组，而组不能属于两个教师。是的，可以有比小组更多的教师。

所以我正在寻找最终的输出如下:

解决方案

Group 1 with Teacher B: 40
Group 2 with Teacher D: 100
Group 3 with Teacher A: 80

我目前的工作
我已经尝试了几种使用 Pandas 解决这个问题的方法，但一切都只获取行和列的最高值，或者充其量是最高的键的名称。我跟着教程here
但没有取得太大的成功。任何指导都会很棒。

Answer 1

这看起来像一个优化问题。

您有 2 种方法来处理它(从理论上讲)。

启发式:

除了病理用例，我们可以认为矩阵中的最高值将在最终结果中结束。这里我们有 100 组 2 和老师 D。然后我们删除组 2 的行和老师 D 的列并迭代。

这一步一步给出:

Group 2    Teacher D   100
Group 3    Teacher A    80
Group 1    Teacher B    50

详尽无遗

前面的方法会导致正确的结果是值有很大的差异，但如果值彼此太接近，则只能找到接近最大值的解决方案。穷举方法包括计算每个可能组合的值的总和并保持最高值。它当然会给出相同的结果，但是我需要太多的操作才能在这里手动显示它...

Python 翻译

第一种方法是迭代但很简单:

# heuristic

dfA = df
result = {}

while (len(dfA) > 0):
    mx = dfA.max()     # find max per teacher
    mmx = pd.Series(mx[mx == mx.max()])  # find absolute max of matrix
    teacher = mmx.index[0]                       # get teacher
    val = mmx.values[0]                          # get value
    group = dfA[dfA[teacher] == val].index[0]    # get group
    result[group] = (teacher, val)               # store the triplet
    dfA = dfA.drop(index = group).drop(columns = teacher) # remove the row and column

dfout = pd.DataFrame(result).T
print(dfout.to_string())

按预期提供:

                 0    1
Group 2  Teacher D  100
Group 3  Teacher A   80
Group 1  Teacher B   40

第二种方法更具确定性，但可能无法扩展到大型数据集:

import itertools

# compute with itertools all the possible permutations of group-teachers
mindex = pd.MultiIndex.from_tuples(itertools.permutations(df.columns, len(df)))

# compute the total value for each permutation
total = pd.DataFrame(data = 0, columns=mindex, index=df.index
                     ).transform(lambda x: pd.Series(
                         [df.loc[x.index[i], x.name[i]]
                          for i in range(len(x))], index=x.index)).sum()

# prepare the resulting dataframe
dfout = pd.DataFrame({'Groups': df.index,
                      'Teachers': total[total == total.max()].index[0]})

# extract the value per group
dfout['val'] = dfout.apply(lambda x: df.loc[x['Groups'], x['Teachers']], axis=1)

print(dfout.to_string())

它提供与预期相同的值

    Groups   Teachers  val
0  Group 1  Teacher B   40
1  Group 2  Teacher D  100
2  Group 3  Teacher A   80