問題：我想在矩陣中找到每個老師和小組的最高值，以最大化哪個小組應該和哪個老師一起去的比例。 Teacher A Teacher B Teacher C Teacher DGroup 1 50 40 20 50Group 2 30 10 40 100Group 3 80 60 40 20在上表中。我知道如何找出行和列中的最高值，但我想在教師和組的組合中找到最高值，即教師不能屬于兩個組，而組不能屬于兩個教師。是的，可以有比小組更多的教師。所以我正在尋找最終輸出如下：解決方案Group 1 with Teacher B: 40Group 2 with Teacher D: 100Group 3 with Teacher A: 80到目前為止，我的工作已經嘗試了幾種使用pandas 解決此問題的方法，但所有內容都只獲取行和列的最高值，或者最多獲取最高鍵的名稱。我按照這里的教程進行操作， 但沒有取得太大的成功。任何指導都會很棒。
3 回答
慕村9548890
TA貢獻1884條經驗 獲得超4個贊
首先搜索所有可能的排列，然后取最大值作為值的總和，最后打印出來。這是我使用數據框的實現：
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
阿波羅的戰車
TA貢獻1862條經驗 獲得超6個贊
這看起來像一個優化問題。
你有兩種方法來處理它（從理論上講）。
啟發式：
除了病態用例，我們可以認為矩陣中的最高值將在最終結果中結束。這里我們有 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
慕哥6287543
TA貢獻1831條經驗 獲得超10個贊
計算行和列的最佳組合以優化轉換。我使用了使用匈牙利算法的linear_sum_assignment包。更多可以在這里找到
from scipy.optimize import linear_sum_assignment
import pandas as pd
df = pd.read_csv("myfile.csv", index_col=0)
gain = df.to_numpy()
row_ind, col_ind = linear_sum_assignment(gain, maximize=True)
print(row_ind)
print(col_ind)
print(gain[row_ind, col_ind].sum())
添加回答
舉報
0/150
提交
取消