Skip to content

nikiforosbotis/StableMarriage

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

15 Commits
 
 
 
 
 
 
 
 

Repository files navigation

StableMarriage

This code contains a Python script with the implementation of the Gale-Shapley algorithm

In the problem of Stable Marriage we are looking for a stable matching between men and women having as input the preferences of both males.

In our case, the preferences are given through JSON files:

{
  "men_rankings": {
    "abe": ["cat", "bea", "ada"],
    "bob": ["ada", "cat", "bea"],
    "cal": ["ada", "bea", "cat"]
  },

  "women_rankings": {
    "ada": ["abe", "cal", "bob"],
    "bea": ["bob", "abe", "cal"],
    "cat": ["cal", "abe", "bob"]
  }
}

The program's output is also given as a JSON file:

{"abe": "cat", "bob": "bea", "cal": "ada"}

If we start tackling the problem from men's part, the solution that is produced is optimized for them (as the above). On the other hand, if we tackle it from the women's part, the solution should be optimized for the women:

{"ada": "abe", "bea": "bob", "cat": "cal"}

The program can be run with the following ways:

  • python3 stable_marriage.py -m <input_filename>, which outputs the solution that is optimized for the men. The script produces a JSON representation of the solution: { "man": "woman", "another_man": "another_woman", ...}.
  • python3 stable_marriage.py -m <input_filename> -o <output_filename>, which also outputs the solution that is optimized for the men. The script is saved on a file named output_filename.
  • python3 stable_marriage.py -w <input_filename>, which outputs the solution that is optimized for the women. The script produces a JSON representation of the solution: { "woman": "man", "another_woman": "another_man", ...}.
  • python3 stable_marriage.py -w <input_filename> -o <output_filename>, which also outputs the solution that is optimized for the women. The script is saved on a file named output_filename.

Example files for input-output:

The full program's description (in Greek) can be found here.

About

Implementation of the Gale-Shapley algorithm in Python

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages