Some time ago I started to interest myself in algorithms. Thus, I bought 2 books about them and I started to read 🙂
The first problem in the first book was explaining the Stable Matching Problem. The essence of the problem is that if you have n males and n females, all of which wanting to get married, you should come up with an algorithm to propose who should marry who. Or if we use the terms from wikipedia:
The stable marriage problem (also stable matching problem or SMP) is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. A matching is a mapping from the elements of one set to the elements of the other set. A matching is stable whenever it is not the case that both: some given element A of the first matched set prefers some given element B of the second matched set over the element to which A is already matched, and B also prefers A over the element to which B is already matched.
Thus, I have checked the solution of the problem with the G-S algorithm and I saw that it takes less than 20 lines for the description. Thus, I tought that it can probably be something that I can mimic in Python. And so I started doing this about 3 hours ago. This is what I did:
- Creating two lists – one for males and one for females.
- In the lists, adding a dictionary with some properties of the users.
- Developing of useful functions, that were used in my code.
- Lots of tests until I come up with something reasonable.
The functions I have thought that will be useful for me were the following:
- break_engagement(person) – breaking the engagement of someone;
- is_engaged_to(person) – checking what is the name of the person someone is engaged to;
- is_engaged(person) – just a boolean, returning whether the person is engaged;
- who_do_you_love_more(person, candidate1, candidate2) – checking for the position of candidate1 and candidate2 in the list of the person;
- engage(dramaKing, dramaQueen) – setting the King and the Queen to engagement;
- get_name_from_ranking(dramaKing, rank) – this takes the name of the n-th unit in the list of the dramaKing;
- main() – not going to explain it;
- happyend() – printing the engaged couples, after the main is ran.
So, after I started with something like this:
|
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 |
males = [ { "name": "A", "preferences": ["10", "20", "30", "40", "50", "60"], }, { "name": "B", "preferences": ["20", "30", "50", "10", "40", "60"], }, { "name": "C", "preferences": ["20", "30", "10", "50", "40", "60"], }, { "name": "D", "preferences": ["20", "30", "10", "50", "40", "60"], }, { "name": "E", "preferences": ["10", "30", "20", "50", "40", "60"], }, { "name": "F", "preferences": ["20", "30", "10", "50", "40", "60"], }, ] females = [ { "name": "10", "preferences": ["A", "B", "C", "E", "D", "F"], }, { "name": "20", "preferences": ["C", "A", "B", "D", "E", "F"], }, { "name": "30", "preferences": ["C", "A", "B", "D", "E", "F"], }, { "name": "40", "preferences": ["A", "B", "C", "E", "D", "F"], }, {males = [ { |
So, what can we conclude from the given data inititally? We see that the less wanted male is the one with “F” and the less wanted female is “60”. Concerning the most wanted male, we do not know – we see that “A”, “C” or “B” are the ones on the top. The females are “10” and “20”. Thus, what is the result? A possible one is this:
As you see, we have a stable matching. We even had 3 breakings during it, but that is for the good of the stability – 20 has initially settled an engagement with “B”, but as far as “C” started to loop she decided to go for him. And something similar for F and D. One can write a “Santa-Barbara” generator with Python, if interested.
Pretty much that is all. Here comes the code:
|
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 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 |
males = [ { "name": "A", "is_free": True, "gender": "male", "preferences": ["10", "20", "30", "40", "50", "60"], "engaged_to": "", "proposed_to":[], }, { "name": "B", "is_free": True, "gender": "male", "preferences": ["20", "30", "50", "10", "40", "60"], "engaged_to": "", "proposed_to":[], }, { "name": "C", "is_free": True, "gender": "male", "preferences": ["20", "30", "10", "50", "40", "60"], "engaged_to": "", "proposed_to":[], }, { "name": "D", "is_free": True, "gender": "male", "preferences": ["20", "30", "10", "50", "40", "60"], "engaged_to": "", "proposed_to":[], }, { "name": "E", "is_free": True, "gender": "male", "preferences": ["10", "30", "20", "50", "40", "60"], "engaged_to": "", "proposed_to":[], }, { "name": "F", "is_free": True, "gender": "male", "preferences": ["20", "30", "10", "50", "40", "60"], "engaged_to": "", "proposed_to":[], }, ] females = [ { "name": "10", "is_free": True, "gender": "female", "preferences": ["A", "B", "C", "E", "D", "F"], "engaged_to": "", "proposed_to":[], }, { "name": "20", "is_free": True, "gender": "female", "preferences": ["C", "A", "B", "D", "E", "F"], "engaged_to": "", "proposed_to":[], }, { "name": "30", "is_free": True, "gender": "female", "preferences": ["C", "A", "B", "D", "E", "F"], "engaged_to": "", "proposed_to":[], }, { "name": "40", "is_free": True, "gender": "female", "preferences": ["A", "B", "C", "E", "D", "F"], "engaged_to": "", "proposed_to":[], }, { "name": "50", "is_free": True, "gender": "female", "preferences": ["A", "B", "C", "E", "D", "F"], "engaged_to": "", "proposed_to":[], }, { "name": "60", "is_free": True, "gender": "female", "preferences": ["B", "A", "C", "D", "F", "E"], "engaged_to": "", "proposed_to":[], }, ] def break_engagement(person): breakingWith = is_engaged_to(person) for m in males: if m["name"] == person: if m["engaged_to"] != "": m["engaged_to"] = "" m["is_free"] = True print("{} is breaking with {}.".format(person, breakingWith)) for f in females: if f["name"] == person: if f["engaged_to"] != "": f["engaged_to"] = "" m["is_free"] = True print("{} is breaking with {}.".format(person, breakingWith)) def is_engaged_to(person): for m in males: if m["name"] == person: return m["engaged_to"] for f in females: if f["name"] == person: return f["engaged_to"] return False def is_engaged(person): for m in males: if m["name"] == person: if m["engaged_to"] != "": return True for f in females: if f["name"] == person: if f["engaged_to"] != "": return True return False def who_do_you_love_more(person, candidate1, candidate2): for m in males: if m["name"] == person: for x in range(0, len(males)): if candidate1 == m["preferences"][x]: return candidate1 if candidate2 == m["preferences"][x]: return candidate2 for f in females: if f["name"] == person: for x in range(0, len(males)): if candidate1 == f["preferences"][x]: return candidate1 if candidate2 == f["preferences"][x]: return candidate2 def engage(dramaKing, dramaQueen): for m in males: if m["name"] == dramaKing: m["engaged_to"] = dramaQueen m["is_free"] = False for f in females: if f["name"] == dramaQueen: f["engaged_to"] = dramaKing f["is_free"] = False def get_name_from_ranking(dramaKing, rank): for m in males: if m["name"] == dramaKing: return m["preferences"][rank] def main(): while (True): numberOfPairs = len(males) good = 1 for m in males: dramaKing = m["name"] if (m["is_free"] == False) and (len(m["proposed_to"]) != numberOfPairs): good += 1 if good == numberOfPairs: print("\n\n\nSuccess!") return for x in range(0, numberOfPairs): if not is_engaged(dramaKing): if x not in m["proposed_to"]: m["proposed_to"].append(x) woman = get_name_from_ranking(dramaKing, x) if is_engaged(woman): currentManOfTheEngaged = is_engaged_to(woman) betterLover = who_do_you_love_more( woman, currentManOfTheEngaged, dramaKing) engage(betterLover, woman) if betterLover != currentManOfTheEngaged: break_engagement(currentManOfTheEngaged) else: engage(dramaKing, woman) def happyend(): print("Resolution:\n") for m in males: dramaKing = m["name"] dramaQueen = m["engaged_to"] print("{} <---> {}".format(dramaKing, dramaQueen)) main() happyend() |
Enjoy it!