Job-optimal stable matching pairing solver template

stable_matching.py

class StableMatching():
  def solve(self, job_prefs: dict, candidates_prefs: dict) -> list(tuple(str, int)):
    """
    Returns a job-optimal stable matching pairing that gives equilibria (¬∃ x=(C*, J*) s.t. x ∉ solution set).
    ---------------------
    | Jobs | Candidates |
    ---------------------
    |   1  |  A > B > C |
    ---------------------
    |   2  |  B > A > C |
    ---------------------
    |   3  |  A > B > C |
    ---------------------
    
    ---------------------------
    | Candidates |    Jobs    |
    ---------------------------
    |      A     |  2 > 1 > 3 |
    ---------------------------
    |      B     |  1 > 3 > 2 |
    ---------------------------
    |      C     |  1 > 2 > 3 |
    ---------------------------
    
    >>> job_prefs = {1: ('A', 'B', 'C'), 2: ('B', 'A', 'C'), 3: ('A', 'B', 'C')}
    >>> candidates_prefs = {'A': (2, 1, 3), 'B': (1, 3, 2), 'C': (1, 2, 3)}
    >>> StableMatching().solve(job_prefs, candidates_prefs).sort()
    [('A', 2), ('B', 1), ('C', 3)]
    """
    rejects = 0
    output = []
    for candidate in candidates_prefs:
      output.append([candidate])
    while rejects == 0:
      # morning
      # TODO
      
      # afternoon
      # TODO
      
      # evening
      # TODO
    return [tuple(x) for x in output]