Python 3 Gale-Shapley Algorithm Script to Solve Stable Marriage Problem on Command Line Full Project For Beginners

 

 

app.py

 

 

preffered_ranking_men = {
	'Ryan' : ['Lizzy', 'Sarah', 'Zoey', 'Daniella'],
	'Joe' : ['Sarah', 'Lizzy', 'Daniella', 'Zoey'],
	'Blake' : ['Sarah', 'Daniella', 'Zoey', 'Lizzy'],
	'Connor' : ['Lizzy', 'Sarah', 'Zoey', 'Daniella'],
}

preffered_ranking_women = {
	'Lizzy' : ['Ryan', 'Blake', 'Joe', 'Connor'],
	'Sarah' : ['Ryan', 'Blake', 'Connor', 'Joe'],
	'Zoey' : ['Connor', 'Joe', 'Ryan', 'Blake'],
	'Daniella' : ['Ryan', 'Joe', 'Connor', 'Blake'],
}

tentative_matches = [] # To keep track of the tentative matchings
free_men = [man for man in list(preffered_ranking_men.keys())] # Initialize the list of free men

def stableMatch():
	'''
	Run the algorithm till stable match terminates
	'''
	while len(free_men) > 0:
		for man in free_men:
			begin_matching(man)

def begin_matching(man):
	'''
	This function takes a man as argument and matches him to a potential partner
	'''
	print(f"Dealing with {man}")
	for woman in preffered_ranking_men[man]:
		taken_match = [pairing for pairing in tentative_matches if woman in pairing]

		if not taken_match:
			# if the woman is not taken, match her tentatively with the man
			tentative_matches.append([man, woman])
			free_men.remove(man)
			print(f"{man} is tentatively matched to {woman}")
			break

		else:
			print(f"{woman} is already matched")
			current_partner = preffered_ranking_women[woman].index(taken_match[0][0])
			potential_partner = preffered_ranking_women[woman].index(man)
			'''
			Compare the ranking of the woman's current partner and the potential partner
			'''
			if potential_partner < current_partner:
				print(f"{man} is more preffered than {taken_match[0][0]}")
				print(f"Unpair {taken_match[0][0]} and {woman}. Now, {man} is tentatively matched to {woman}")

				# the potential guy is matched and the current guy is now free
				free_men.remove(man)
				free_men.append(taken_match[0][0])

				taken_match[0][0] = man
				break
			else:
				print(f"{woman} is satisfied with {taken_match[0][0]}")

if __name__ == '__main__':
	stableMatch()
	print("\nFINAL PAIRINGS : ")
	print(*tentative_matches) # print out the final list of matchings

 

See also  Python 3 Tkinter Script to Build Multiplayer People Chat Window UI Widget in GUI Desktop App Full Project For Beginners

 

stable-matching

Implementing the Gale-Shapley algorithm to solve the Stable Marriage Problem

How to Use

  • Command line utility
  • Simply add the preferences in the code as shown and run the file to get the results
preffered_ranking_men = {
	'1' : ['C', 'B', 'E', 'A', 'D'],
	'2' : ['A', 'B', 'E', 'C', 'D'],
	'3' : ['D', 'C', 'B', 'A', 'E'],
	'4' : ['A', 'C', 'D', 'B', 'E'],
	'5' : ['A', 'B', 'D', 'E', 'C']
}

preffered_ranking_women = {
	'A' : ['3', '5', '2', '1', '4'],
	'B' : ['5', '2', '1', '4', '3'],
	'C' : ['4', '3', '5', '1', '2'],
	'D' : ['1', '2', '3', '4', '5'],
	'E' : ['2', '3', '4', '1', '5']
}

Leave a Reply