One function
gale_shapley in jilljenn/tryalgo
The author described this change as “fix gale shapley”. It counts as a record because the check below fails on the code as it stood at 96a81ccb1 and passes on 82ebd603a, with nothing else changed between the two runs.
Projectjilljenn/tryalgo
Fix saved2023-02-03
Sharing licenceMIT · LICENSE
Change size+6 −6
What the code was meant to do, written into the code itself as a docstring
Stable matching by Gale-Shapley :param men: table of size n, men[i] is preference list of women for men i :param women: similar :returns: matching table, from women to men :complexity: :math:`O(n^2)`
The change
| 8 | 8 | """ | |
| 9 | 9 | n = len(men) | |
| 10 | 10 | assert n == len(women) | |
| 11 | - | current_suitor = [0] * n | |
| 12 | - | spouse = [None] * n | |
| 11 | + | current_suitor = [0] * n # nb of matchings so far | |
| 12 | + | spouse = [None] * n # current matching | |
| 13 | 13 | rank = [[0] * n for j in range(n)] # build rank | |
| 14 | 14 | for j in range(n): | |
| 15 | 15 | for r in range(n): | |
| 16 | 16 | rank[j][women[j][r]] = r | |
| 17 | - | singles = deque(range(n)) # all men are single and get in the queue | |
| 17 | + | singles = list(range(n)) # initially all men are single | |
| 18 | 18 | while singles: | |
| 19 | - | i = singles.popleft() | |
| 20 | - | j = men[i][current_suitor[i]] | |
| 19 | + | i = singles.pop() | |
| 20 | + | j = men[i][current_suitor[i]] # propose matching (i,j) | |
| 21 | 21 | current_suitor[i] += 1 | |
| 22 | 22 | if spouse[j] is None: | |
| 23 | 23 | spouse[j] = i | |
| 24 | 24 | elif rank[j][spouse[j]] < rank[j][i]: | |
| 25 | 25 | singles.append(i) | |
| 26 | 26 | else: | |
| 27 | - | singles.put(spouse[j]) # sorry for spouse[j] | |
| 27 | + | singles.append(spouse[j]) # sorry for spouse[j] | |
| 28 | 28 | spouse[j] = i | |
| 29 | 29 | return spouse |
The check that tells the two apart
fail→pass·tests/test_tryalgo.py::TestTryalgo::test_gale_shapley
Check file tests/test_tryalgo.py, taken without changes from the fix and copied onto the older code, so the exact same check runs against both versions.
Origin and history
The code before it96a81ccb1c204631218dcabfd3526b6c35a6f9a5
Broken version dated2023-01-25
Moduletryalgo.gale_shapley
Units changedgale_shapley
Fingerprint45bb40e6e6c9033c
Checked2026-08-18 by goldset/0.1
Every field above is generated by our program. None of it is written by hand.