1 files changed, 188 insertions, 0 deletions

diff --git a/stable.py b/stable.py
new file mode 100644
index 0000000..f3bb84e
--- /dev/null
+++ b/stable.py
@@ -0,0 +1,188 @@
+#!/usr/bin/env python
+
+# The gale_shapley implementation is taken from
+# https://johnlekberg.com/blog/2020-08-22-stable-matching.html
+
+from collections import deque
+
+# Track the number of total proposals per proposer for order O questions
+number_of_proposals = dict()
+
+
+def pref_to_rank(pref):
+    return {a: {b: idx for idx, b in enumerate(a_pref)} for a, a_pref in pref.items()}
+
+
+def gale_shapley(*, A, B, A_pref, B_pref):
+    """Create a stable matching using the
+    Gale-Shapley algorithm.
+
+    A -- set[str].
+    B -- set[str].
+    A_pref -- dict[str, list[str]].
+    B_pref -- dict[str, list[str]].
+
+    Output: list of (a, b) pairs.
+    """
+    B_rank = pref_to_rank(B_pref)
+    ask_list = {a: deque(bs) for a, bs in A_pref.items()}
+    pair = {}
+
+    remaining_A = set(A)
+    while len(remaining_A) > 0:
+        a = remaining_A.pop()
+        b = ask_list[a].popleft()
+        if b not in pair:
+            pair[b] = a
+            print(f"Matching {a} with {b} (a)")
+            number_of_proposals[a] += 1
+        else:
+            a0 = pair[b]
+            b_prefer_a0 = B_rank[b][a0] < B_rank[b][a]
+            if b_prefer_a0:
+                remaining_A.add(a)
+                print(f"{a} is rejected by {b} because {a0} is more preffered (c)")
+                number_of_proposals[a] += 1
+            else:
+                remaining_A.add(a0)
+                print(f"Matching {a} with {b}, {a0} is now free (b)")
+                number_of_proposals[a] += 1
+                pair[b] = a
+
+    return [(a, b) for b, a in pair.items()]
+
+
+if __name__ == "__main__":
+
+    women = list(range(1, 27))
+    men = [chr(x + 65) for x in range(26)]
+
+    n = int(input("n: "))
+
+    men = men[:n]
+    # because algorithms are 1 indexed, compromise
+    women = ["0"] + women[:n]
+
+    men_pref = dict()
+    women_pref = dict()
+
+    # For 1 to n-1, men's preference lists look like
+    # Mk = Wk Wk+1 ... Wn-1 W1 W2 ... Wn
+
+    for (cur, m) in enumerate(men, start=1):
+
+        # last man n has the same preference list as n-1
+        if cur == n:
+            cur = cur - 1
+
+        prefs = list()
+        k = cur
+
+        # Wk .. Wn-1
+        while k < n:
+            prefs.append(women[k])
+            k += 1
+
+        # W1 .. Wn-1
+        k = 1
+        while k < cur:
+            prefs.append(women[k])
+            k += 1
+
+        # last woman n is always last at everyone's preference list
+        prefs.append(women[n])
+        men_pref[m] = prefs
+
+    # women's preference list for 1-n-2 look like
+    # Wk = Wk+1 Wk
+
+    # n-1 looks like
+    # Wn-1 = W1 Wn
+
+    # last women's preference list doesn't matter
+
+    for (cur, w) in enumerate(women, start=-1):
+
+        prefs = list()
+
+        # again, compromise between 1 indexed algorithms and nice code
+        if cur == -1:
+            continue
+
+        # last woman
+        if cur == n - 1:
+            k = 0
+            while k < n:
+                prefs.append(men[k])
+                k += 1
+                women_pref[w] = prefs
+            continue
+
+        # n-1th woman
+        if cur == n - 2:
+            prefs.append(men[0])
+            prefs.append(men[n - 1])
+
+            k = 0
+
+            while k < n:
+                if k == n - 1:
+                    k += 1
+                    continue
+                if k == 0:
+                    k += 1
+                    continue
+                prefs.append(men[k])
+                k += 1
+
+            women_pref[w] = prefs
+            continue
+
+        # rest of the women obey the general rule
+        prefs.append(men[cur + 1])
+        prefs.append(men[cur])
+
+        # we need n - k more men to fill, they don't matter
+        k = 0
+
+        while k < n:
+            if k == cur:
+                k += 1
+                continue
+            if k == cur + 1:
+                k += 1
+                continue
+            prefs.append(men[k])
+            k += 1
+
+        women_pref[w] = prefs
+
+    print("Men Preference Table")
+    for (k,v) in men_pref.items():
+        print(f'{k:2}| {" ".join([str(x) for x in v])}')
+
+    print("----")
+
+    print("Women Preference Table")
+    for (k,v) in women_pref.items():
+        print(f'{k:2}| {" ".join(v)}')
+
+    print("----")
+
+    number_of_proposals = {a: 0 for a in men}
+
+    matchings= gale_shapley(A=men, B=women, A_pref=men_pref, B_pref=women_pref)
+
+    print(f"Final pairings:")
+
+    for (m,w) in matchings:
+        print(f"{m} - {w}")
+
+    print()
+
+    total = 0
+    for (men, times) in number_of_proposals.items():
+        total += times
+        print(f"{men} proposed {times} times")
+
+    print(f"total of {total} times with n(n-1) + 1 = {n*(n-1) + 1}")