CODEWITHSUNDEEP
pythonalgorithm
lmngn23
lmngn23

Reputation: 521

python implementation of Gale-shapley algorithm

I have the following implementation problem for the Gale-Shapley algorithm.

The applicant preferences and employers preferences have the form: 

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]]

They are arrays with the indices corresponding to the applicant numbers and employer number. The indices of the sub-array are the preference for a job/applicant.

Therefore, the rankings dictionary have the dictionary form:

The rankings have the following form : 

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}

The keys and values have the format: "applicant,job": rank. I am also given a list of open jobs from 1 to n: 

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

Current job is the matching job of each applicant, initialized to -1 because everyone is unmatched at first

current_job = [-1 for applicant in applicant_prefs]

My task is to implement the algorithm, here is my attempt: 

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)

However, with the above example, the array returned is [3,2,1] instead of [2,3,1]. I think I got close to the right answer.

I would really appreciate any help

Upvotes: 1

Views: 1699

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65498

In Gale--Shapely, the employers make offers to applicants in the order that the employer prefers them. Your code doesn't use the employer preferences and makes offers in the order of increasing applicant ID.

Upvotes: 1

Related Questions