Gale-shapley算法的python实现

Question

我有以下 Gale-Shapley 算法的实现问题。

申请人偏好和雇主偏好的形式为:

applicant_prefs = ['applicant preferences', [2, 1, 3], [1, 3, 2], [1, 3, 2]]   
employer_prefs = ['employer preferences', [3, 1, 2], [3, 2, 1], [2, 3, 1]]

它们是数组，索引对应申请人编号和雇主编号。子数组的索引是工作/申请人的偏好。

因此，排名字典具有字典形式:

排名有以下形式:

rankings = {'1,2': 0, '1,1': 1, '1,3': 2, '2,1': 0, '2,3': 1, '2,2': 2, '3,1': 0, '3,3': 1, '3,2': 2}

键和值的格式为:“applicant,job”: rank。 我还得到了从 1 到 n 的空缺职位列表:

n = len(applicant_prefs) - 1
open_jobs = list(range(1, n+1)) (In this case it's 3)

current job是每个应聘者匹配的工作，初始化为-1，因为一开始每个人都不匹配

current_job = [-1 for applicant in applicant_prefs]

我的任务是实现算法，这是我的尝试:

applicant = 1
while open_jobs:
#traversing through the applicants from applicant 1 to n
    if(applicant <= n):
        newJob = open_jobs.pop()
        # if an applicant does not have a job, they accept.
        if(current_job[applicant] == -1):
            current_job[applicant] = newJob
        else:        
        # if this applicant prefers the offer to their current job :
        # they quit their current job and accept the offer
            if(rankings[str(applicant) + "," + str(newJob)] > rankings[str(applicant) + "," + str(current_job[applicant])]):
                open_jobs.append(current_job[applicant])
                current_job[applicant] = newJob
            else:
                open_jobs.append(newJob)
    applicant += 1  

 print(current_job)

但是，对于上面的示例，返回的数组是 [3,2,1] 而不是 [2,3,1]。我想我已经接近正确答案了。

如果有任何帮助，我将不胜感激

Answer 1

在 Gale--Shapely 中，雇主按照雇主喜欢他们的顺序向申请人发出要约。您的代码不使用雇主偏好，而是按照申请人 ID 递增的顺序提供报价。