|
| 1 | +from typing import List |
| 2 | + |
| 3 | + |
| 4 | +def stable_matching(donor_pref: List[int], recipient_pref: List[int]) -> List[int]: |
| 5 | + """ |
| 6 | + Finds the stable match in any bipartite graph, i.e a pairing where no 2 objects |
| 7 | + prefer each other over their partner. The function accepts the preferences of |
| 8 | + oegan donors and recipients (where both are assigned numbers from 0 to n-1) and |
| 9 | + returns a list where the index position corresponds to the donor and value at the |
| 10 | + index is the organ recipient. |
| 11 | +
|
| 12 | + To better understand the algorithm, see also: |
| 13 | + https://github.com/akashvshroff/Gale_Shapley_Stable_Matching (README). |
| 14 | + https://www.youtube.com/watch?v=Qcv1IqHWAzg&t=13s (Numberphile YouTube). |
| 15 | +
|
| 16 | + >>> donor_pref = [[0, 1, 3, 2], [0, 2, 3, 1], [1, 0, 2, 3], [0, 3, 1, 2]] |
| 17 | + >>> recipient_pref = [[3, 1, 2, 0], [3, 1, 0, 2], [0, 3, 1, 2], [1, 0, 3, 2]] |
| 18 | + >>> print(stable_matching(donor_pref, recipient_pref)) |
| 19 | + [1, 2, 3, 0] |
| 20 | + """ |
| 21 | + assert len(donor_pref) == len(recipient_pref) |
| 22 | + n = len(donor_pref) |
| 23 | + unmatched_donors = list(range(n)) |
| 24 | + donor_record = [-1] * n # who the donor has donated to |
| 25 | + rec_record = [-1] * n # who the recipient has received from |
| 26 | + num_donations = [0] * n |
| 27 | + while unmatched_donors: |
| 28 | + donor = unmatched_donors[0] |
| 29 | + donor_preference = donor_pref[donor] |
| 30 | + recipient = donor_preference[num_donations[donor]] |
| 31 | + num_donations[donor] += 1 |
| 32 | + rec_preference = recipient_pref[recipient] |
| 33 | + prev_donor = rec_record[recipient] |
| 34 | + if prev_donor != -1: |
| 35 | + if rec_preference.index(prev_donor) > rec_preference.index(donor): |
| 36 | + rec_record[recipient] = donor |
| 37 | + donor_record[donor] = recipient |
| 38 | + unmatched_donors.append(prev_donor) |
| 39 | + unmatched_donors.remove(donor) |
| 40 | + else: |
| 41 | + rec_record[recipient] = donor |
| 42 | + donor_record[donor] = recipient |
| 43 | + unmatched_donors.remove(donor) |
| 44 | + return donor_record |
0 commit comments