-
Notifications
You must be signed in to change notification settings - Fork 2
/
2stableroommates.py
174 lines (161 loc) · 5.25 KB
/
2stableroommates.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
import copy, sys, csv, os
csv_f = csv.reader(open('preferences.csv', 'rU'))
problem = csv_f.next()[0].lower()
# csv file does not correctly indicate stable marriage or
# hospital resident as the problem to be solved
if (problem != "stable roommates" and problem != "stable roommate"):
if (problem == "stable marriage" or problem == "hospital resident"):
print("preferences.csv indicates stable marriage or hospital resident as the problem rather than stable roommates.")
print("\nPlease choose a new problem in the menu or edit the problem name in preferences.csv")
else:
print("\n\npreferences.csv does not indicate a possible problem.")
print("Please change the problem name in preferences.csv to \nstable marriage, hospital resident, or stable roommates.")
print("Then make the appropriate problem choice.")
os.system("python menu.py")
num_roommates = int(csv_f.next()[0])
# fills in all the students from the csv file into
# the people dictionary as keys
people = {}
for i in xrange(0, num_roommates):
s1 = csv_f.next()[0]
s2 = csv_f.next()[0]
people[s1] = s2.split(' ')
# generates a dictionary rank given the people dictionary
# such that rank[y,x] is y's rank on x's list
def fillRank(people):
rank = {}
for k in people.keys():
rank[k] = {}
for v in people[k]:
rank[k][v] = people[k].index(v)
return rank
rank = fillRank(people)
# Given a person x and a position i,
# this function will return a tuple (y,r) where
# y is the person of rank i on x's preference list
# and r is the rank of x in y's preference list.
def GetPersonRank(x,i):
y = people[x][i]
r = rank[y][x]
return (y,r)
# current best possible roommate 'x' is proposing to
best = {}
# rank of x's most feasible roommate choice
bestrank = {}
# person whose proposal x has but isn't x's top choice
worst = {}
# rank of worst in x's list
worstrank = {}
# boolean
holds_proposal = {}
# the next best person that x would accept
second = {}
# second's rank on x's list
secondrank = {}
# rank of x on second[x]'s preference list,
# ie. how second[x] perceives x
secondperception = {}
# PhaseI creates plausible semi-matchings
# between roommates
def phaseI():
# initializing
for k in people.keys():
n = len(people.keys())
holds_proposal[k] = False
worst[k] = k
worstrank[k] = n
bestrank[k] = 0
# creates semi-engagements (plausible matches)
for k in people.keys():
proposer = k
while True:
# next is the k's top choice, rank is best's perception of k
(next, rank) = GetPersonRank(proposer, bestrank[proposer])
# next prefers its current match better than k
while (rank > worstrank[next]):
# proposer must move on
bestrank[proposer] = bestrank[proposer] + 1
(next, rank) = GetPersonRank(proposer, bestrank[proposer])
# previous proposed to next
previous = worst[next]
worstrank[next] = rank
worst[next] = proposer
best[proposer] = next
proposer = previous
if (holds_proposal[next] == False):
break
holds_proposal[next] = True
if (bestrank[proposer] == n):
# can only be engaged to self, no stable match
return False
# move onto phaseII, there may be stable match
return True
cycle = []
# finds the potential "rotations" for previous semi-matching
# to be broken apart to form new matches
def seekCycle():
for k in people.keys():
# find unmatched person
if (bestrank[k] < worstrank[k]):
break
# no unmatched person found -> return empty cycle, no work!
if (bestrank[k] >= worstrank[k]):
return (0,0,"")
# unmatched person found
else :
last = 1
while True:
cycle[last] = k
last = last + 1
p = bestrank[k]
while True:
# find second choice
p = p + 1
(y,r) = GetPersonRank(k,p)
# y would accept because k is higher in rank
if (r <= worstrank[y]):
break
# saving the second choice
secondrank[k] = p
second[k] = y
secondperception[k] = r
k = worst[second[x]]
if (k in cycle):
break
last = last - 1
first = last - 1
# start cycle again
while (cycle[first] != k):
first = first - 1
return (first, last, cycle)
# based on seekCycle results
cycle2 = []
def phaseII():
solution_possible = True
solution_found = False
while (solution_possible and not solution_found):
(first, last, cycle) = seekCycle()
# stable rooming matches are already present
if (cycle == ""):
solution_found = True
else:
cycle2 = cycle[first:last]
# executing the switches and new arrangements
for i in range(cycle2):
bestrank[k] = secondrank[k]
worstrank[best[k]] = secondperception[k]
worst[best[k]] = k
for i in range(cycle2):
# gone through everybody, no stable match is possible
if (bestrank[k] > worstrank[k]):
solution_possible = False
return solution_found
# output of the matching results (or that no matching is possible)
if not phaseI() or not phaseII():
print("There is no stable rooming situation")
else:
print("\n Rooming Results \n")
for k in best.keys():
print("Person: %s" % k)
print("Best Roommate Match: %s \n" % best[k])
os.system("python menu.py")