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

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解决这个问题的方法，但一切都只获取行和列的最高值，或者充其量是最高的键的名称。我在这里学习了教程， 但没有取得太大的成功。任何指导都会很棒。

Answer 1

首先搜索所有可能的排列，然后取值之和的最大值，最后打印它。这是我使用数据框的实现：

import itertools
m = [
    [50, 40, 20, 50],
    [30, 10, 40, 100],
    [80, 60, 40, 20]
]
rows = ['Group 1', 'Group 2', 'Group 3']
cols = ['Teacher A', 'Teacher B', 'Teacher C', 'Teacher D']
df = pd.DataFrame(m, index=rows, columns=cols)

permuts = itertools.permutations(cols, len(rows))

L = []
for p in permuts:
    s = 0
    d = {}
    for i, r in enumerate(rows):
        s += df[p[i]][r]
        d[r] = p[i]
    obj = [s, d]
    L.append(obj)

result = max(L, key=lambda x: x[0])
# [220, {'Group 1': 'Teacher B', 'Group 2': 'Teacher D', 'Group 3': 'Teacher A'}]
# Here 220 is the maximum sum you can have

result_dict = result[1]
# {'Group 1': 'Teacher B', 'Group 2': 'Teacher D', 'Group 3': 'Teacher A'}

for i, v in result_dict.items():
    print("{} with {} : {}".format(i, v, df[v][i]))

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

说明

这是一个如何工作的小例子itertools.permutations。该数字2是每个排列的长度，并且['a','b','c']是排列的元素：

import itertools
permuts = itertools.permutations(['a','b','c'],2)
for i in a:
    print(i)

输出：（这里有 6 种排列）

('a', 'b')
('a', 'c')
('b', 'a')
('b', 'c')
('c', 'a')
('c', 'b')

在我们的例子中，我们有 3 个组，因此我们需要 4 名教师中的 3 名（教师 A、B、C 和 D）。例如排列('Teacher A', 'Teacher B', 'Teacher C')意味着Group1=Teacher A, Group2=Teacher B, Group3=Teacher C)。

因此，我们将枚举 3 位教师的所有有序排列permuts = itertools.permutations(cols, len(rows))：

('Teacher A', 'Teacher B', 'Teacher C')
('Teacher A', 'Teacher B', 'Teacher D')
('Teacher A', 'Teacher C', 'Teacher B')
...
('Teacher D', 'Teacher C', 'Teacher A')
('Teacher D', 'Teacher C', 'Teacher B')

所以我们的变量中有 24 个元组permuts

然后我们计算每个排列的值的总和，我们得到一个包含这些元素的大列表：

L = []
for p in permuts:
    s = 0
    d = {}
    for i, r in enumerate(rows):
        s += df[p[i]][r]
        d[r] = p[i]
    obj = [s, d]
    L.append(obj)

输出L：

[
    [100, {'Group 1': 'Teacher A', 'Group 2': 'Teacher B', 'Group 3': 'Teacher C'}]
    [80, {'Group 1': 'Teacher A', 'Group 2': 'Teacher B', 'Group 3': 'Teacher D'}]
...
    [220, {'Group 1': 'Teacher B', 'Group 2': 'Teacher D', 'Group 3': 'Teacher A'}]
]
...

第一个数字（例如 100、80 和 220）表示此特定排列的值之和。

然后我们选择总和最大的排列，这里是220

result = max(L, key=lambda x: x[0])
# [220, {'Group 1': 'Teacher B', 'Group 2': 'Teacher D', 'Group 3': 'Teacher A'}]

最后，我们使用数据帧中的值打印排列print("{} with {} : {}".format(i, v, df[v][i]))。例如df["Teacher B"]["Group 1"] = 40：

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