aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorYigit Sever2020-11-09 03:11:55 +0300
committerYigit Sever2020-11-09 03:11:55 +0300
commiteea912b9c327d397197212e326b7f2728d59a306 (patch)
tree89e203e9997c693db0999dc16aabca161309d790
parent44093683acd6170fff2c78ab4f0283b36a2943ea (diff)
downloadhw1-master.tar.gz
hw1-master.tar.bz2
hw1-master.zip
Add used python scriptsHEADmaster
-rw-r--r--analysis.py14
-rw-r--r--evlilik_salonu.py104
-rw-r--r--stable.py188
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 @@
1import math
2
3for overs in range(1,8):
4 steps = 0
5 i = 2
6 n = pow(10, overs)
7 while i < n:
8 j = 1
9 while j < n:
10 steps = steps + 1
11 j = j * i
12 i += 1
13
14 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 @@
1women = list(range(1,27))
2men = [chr(x + 65) for x in range(26)]
3
4n = int(input("Give n "))
5
6men = men[:n]
7women = ["0"] + women[:n]
8
9men_pref = dict()
10women_pref = dict()
11
12for (cur, m) in enumerate(men, start=1):
13
14 # last man is the same as one before last man
15 if cur == n:
16 cur = cur - 1
17
18 # Mk = Wk Wk+1 ... Wn-1 W1 W2 ... Wn
19 prefs = list()
20 k = cur
21
22 # Wk ... Wn-1
23 while k < n:
24 prefs.append(women[k])
25 k += 1
26
27 # W1 .. Wn-1
28 k = 1
29 while k < cur:
30 prefs.append(women[k])
31 k += 1
32
33 # last woman is always last
34 prefs.append(women[n])
35 men_pref[m] = prefs
36
37# Wk = Wk+1 Wk
38
39for (cur, w) in enumerate(women, start=-1):
40
41 prefs = list()
42
43 if cur == -1:
44 continue
45
46 if cur == n-1:
47 print("This is useless")
48 k = 0
49 while k < n:
50 prefs.append(men[k])
51 k += 1
52 women_pref[w] = prefs
53 continue
54
55 if cur == n - 2:
56 print(f">>>{w}")
57 # W1 Wcur
58 print(f"appending {men[0]}")
59 prefs.append(men[0])
60 print(f"appending {men[n-1]}")
61 prefs.append(men[n-1])
62
63 print(">>>>>>>")
64 print(prefs)
65 print(">>>>>>>")
66
67 k = 0
68
69 while k < n:
70 if k == n-1:
71 k += 1
72 continue
73 if k == 0:
74 k += 1
75 continue
76 prefs.append(men[k])
77 k += 1
78
79 women_pref[w] = prefs
80 print(">>>>>>>")
81 print(women_pref[w])
82 print("<<<<<<<")
83 continue
84
85 prefs.append(men[cur+1])
86 prefs.append(men[cur])
87
88 # we need n - k more men
89 k = 0
90
91 while k < n:
92 if k == cur:
93 k += 1
94 continue
95 if k == cur + 1:
96 k += 1
97 continue
98 prefs.append(men[k])
99 k += 1
100
101 women_pref[w] = prefs
102
103print(women_pref)
104print(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 @@
1#!/usr/bin/env python
2
3# The gale_shapley implementation is taken from
4# https://johnlekberg.com/blog/2020-08-22-stable-matching.html
5
6from collections import deque
7
8# Track the number of total proposals per proposer for order O questions
9number_of_proposals = dict()
10
11
12def pref_to_rank(pref):
13 return {a: {b: idx for idx, b in enumerate(a_pref)} for a, a_pref in pref.items()}
14
15
16def gale_shapley(*, A, B, A_pref, B_pref):
17 """Create a stable matching using the
18 Gale-Shapley algorithm.
19
20 A -- set[str].
21 B -- set[str].
22 A_pref -- dict[str, list[str]].
23 B_pref -- dict[str, list[str]].
24
25 Output: list of (a, b) pairs.
26 """
27 B_rank = pref_to_rank(B_pref)
28 ask_list = {a: deque(bs) for a, bs in A_pref.items()}
29 pair = {}
30
31 remaining_A = set(A)
32 while len(remaining_A) > 0:
33 a = remaining_A.pop()
34 b = ask_list[a].popleft()
35 if b not in pair:
36 pair[b] = a
37 print(f"Matching {a} with {b} (a)")
38 number_of_proposals[a] += 1
39 else:
40 a0 = pair[b]
41 b_prefer_a0 = B_rank[b][a0] < B_rank[b][a]
42 if b_prefer_a0:
43 remaining_A.add(a)
44 print(f"{a} is rejected by {b} because {a0} is more preffered (c)")
45 number_of_proposals[a] += 1
46 else:
47 remaining_A.add(a0)
48 print(f"Matching {a} with {b}, {a0} is now free (b)")
49 number_of_proposals[a] += 1
50 pair[b] = a
51
52 return [(a, b) for b, a in pair.items()]
53
54
55if __name__ == "__main__":
56
57 women = list(range(1, 27))
58 men = [chr(x + 65) for x in range(26)]
59
60 n = int(input("n: "))
61
62 men = men[:n]
63 # because algorithms are 1 indexed, compromise
64 women = ["0"] + women[:n]
65
66 men_pref = dict()
67 women_pref = dict()
68
69 # For 1 to n-1, men's preference lists look like
70 # Mk = Wk Wk+1 ... Wn-1 W1 W2 ... Wn
71
72 for (cur, m) in enumerate(men, start=1):
73
74 # last man n has the same preference list as n-1
75 if cur == n:
76 cur = cur - 1
77
78 prefs = list()
79 k = cur
80
81 # Wk .. Wn-1
82 while k < n:
83 prefs.append(women[k])
84 k += 1
85
86 # W1 .. Wn-1
87 k = 1
88 while k < cur:
89 prefs.append(women[k])
90 k += 1
91
92 # last woman n is always last at everyone's preference list
93 prefs.append(women[n])
94 men_pref[m] = prefs
95
96 # women's preference list for 1-n-2 look like
97 # Wk = Wk+1 Wk
98
99 # n-1 looks like
100 # Wn-1 = W1 Wn
101
102 # last women's preference list doesn't matter
103
104 for (cur, w) in enumerate(women, start=-1):
105
106 prefs = list()
107
108 # again, compromise between 1 indexed algorithms and nice code
109 if cur == -1:
110 continue
111
112 # last woman
113 if cur == n - 1:
114 k = 0
115 while k < n:
116 prefs.append(men[k])
117 k += 1
118 women_pref[w] = prefs
119 continue
120
121 # n-1th woman
122 if cur == n - 2:
123 prefs.append(men[0])
124 prefs.append(men[n - 1])
125
126 k = 0
127
128 while k < n:
129 if k == n - 1:
130 k += 1
131 continue
132 if k == 0:
133 k += 1
134 continue
135 prefs.append(men[k])
136 k += 1
137
138 women_pref[w] = prefs
139 continue
140
141 # rest of the women obey the general rule
142 prefs.append(men[cur + 1])
143 prefs.append(men[cur])
144
145 # we need n - k more men to fill, they don't matter
146 k = 0
147
148 while k < n:
149 if k == cur:
150 k += 1
151 continue
152 if k == cur + 1:
153 k += 1
154 continue
155 prefs.append(men[k])
156 k += 1
157
158 women_pref[w] = prefs
159
160 print("Men Preference Table")
161 for (k,v) in men_pref.items():
162 print(f'{k:2}| {" ".join([str(x) for x in v])}')
163
164 print("----")
165
166 print("Women Preference Table")
167 for (k,v) in women_pref.items():
168 print(f'{k:2}| {" ".join(v)}')
169
170 print("----")
171
172 number_of_proposals = {a: 0 for a in men}
173
174 matchings= gale_shapley(A=men, B=women, A_pref=men_pref, B_pref=women_pref)
175
176 print(f"Final pairings:")
177
178 for (m,w) in matchings:
179 print(f"{m} - {w}")
180
181 print()
182
183 total = 0
184 for (men, times) in number_of_proposals.items():
185 total += times
186 print(f"{men} proposed {times} times")
187
188 print(f"total of {total} times with n(n-1) + 1 = {n*(n-1) + 1}")