时间戳

首页 > 解决方案 > Gale-shapley算法的python实现

python - Gale-shapley算法的python实现

问题描述

我对 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)

当前工作是每个应聘者的匹配工作，初始化为-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]。我想我已经接近正确答案了。

我真的很感激任何帮助

标签： pythonalgorithm

解决方案

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

推荐阅读