3 files changed, 306 insertions, 0 deletions

diff --git a/analysis.py b/analysis.py
new file mode 100644
index 0000000..f9de516
--- /dev/null
+++ b/analysis.py
@@ -0,0 +1,14 @@
+import math
+
+for overs in range(1,8):
+    steps = 0
+    i = 2
+    n = pow(10, overs)
+    while i < n:
+        j = 1
+        while j < n:
+            steps = steps + 1
+            j = j * i
+        i += 1
+
+    print(f"With {n:8} it took {steps:8}")
diff --git a/evlilik_salonu.py b/evlilik_salonu.py
new file mode 100644
index 0000000..139450d
--- /dev/null
+++ b/evlilik_salonu.py
@@ -0,0 +1,104 @@
+women = list(range(1,27))
+men = [chr(x + 65) for x in range(26)]
+
+n = int(input("Give n "))
+
+men = men[:n]
+women = ["0"] + women[:n]
+
+men_pref = dict()
+women_pref = dict()
+
+for (cur, m) in enumerate(men, start=1):
+
+    # last man is the same as one before last man
+    if cur == n:
+        cur = cur - 1
+
+    # Mk = Wk Wk+1 ... Wn-1 W1 W2 ... Wn
+    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 is always last
+    prefs.append(women[n])
+    men_pref[m] = prefs
+
+# Wk = Wk+1 Wk
+
+for (cur, w) in enumerate(women, start=-1):
+
+    prefs = list()
+
+    if cur == -1:
+        continue
+
+    if cur == n-1:
+        print("This is useless")
+        k = 0
+        while k < n:
+            prefs.append(men[k])
+            k += 1
+            women_pref[w] = prefs
+        continue
+
+    if cur == n - 2:
+        print(f">>>{w}")
+        # W1 Wcur
+        print(f"appending {men[0]}")
+        prefs.append(men[0])
+        print(f"appending {men[n-1]}")
+        prefs.append(men[n-1])
+
+        print(">>>>>>>")
+        print(prefs)
+        print(">>>>>>>")
+
+        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
+        print(">>>>>>>")
+        print(women_pref[w])
+        print("<<<<<<<")
+        continue
+
+    prefs.append(men[cur+1])
+    prefs.append(men[cur])
+
+    # we need n - k more men
+    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(women_pref)
+print(men_pref)
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}")