title: python implementation of Gale-shapley algorithm
body: <p>I have the following implementation problem for the Gale-Shapley algorithm. </p>
  
  <p>The applicant preferences and employers preferences have the form: </p>
  
  <pre><code>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]]
  </code></pre>
  
  <p>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. </p>
  
  <p>Therefore, the rankings dictionary have the dictionary form: </p>
  
  <p>The rankings have the following form : </p>
  
  <pre><code>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}
  </code></pre>
  
  <p>The keys and values have the format: "applicant,job": rank.
  I am also given a list of open jobs from 1 to n: </p>
  
  <pre><code>n = len(applicant_prefs) - 1
  open_jobs = list(range(1, n+1)) (In this case it's 3)
  </code></pre>
  
  <p>Current job is the matching job of each applicant, initialized to -1 because everyone is unmatched at first</p>
  
  <pre><code>current_job = [-1 for applicant in applicant_prefs]
  </code></pre>
  
  <p>My task is to implement the algorithm, here is my attempt: </p>
  
  <pre><code>applicant = 1
  while open_jobs:
  #traversing through the applicants from applicant 1 to n
      if(applicant &lt;= 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)] &gt; 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)
  </code></pre>
  
  <p>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. </p>
  
  <p>I would really appreciate any help</p>