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