In [1]:
from matching.games import StableMarriage
import random
from copy import deepcopy
In [2]:
def search_dict_key(dict, value):
    for key, val in dict.items():
        if val == value:
            return key


def check_unstable_pairs(groupA_preferences: dict, groupB_preferences: dict, current_matching: dict):
    unstable_pairs = []  # format: [(a1, b1), (a2, b2), ...]
    for groupA_test in groupA_preferences.keys():
        for groupB_test in [val for val in groupB_preferences.keys() if val != current_matching[groupA_test]]:
            if groupA_preferences[groupA_test].index(groupB_test) < groupA_preferences[groupA_test].index(current_matching[groupA_test]) and groupB_preferences[
                groupB_test].index(groupA_test) < groupB_preferences[groupB_test].index(search_dict_key(current_matching, groupB_test)):
                unstable_pairs.append((groupA_test, groupB_test))
    return unstable_pairs
In [3]:
groupA_preferences = {
    "M": ["A", "C", "T"],
    "K": ["A", "T", "C"],
    "J": ["T", "A", "C"],
}

groupB_preferences = {
    "C": ["J", "M", "K"],
    "T": ["M", "J", "K"],
    "A": ["J", "M", "K"],
}

current_matching = {"M": "T", "K": "A", "J": "C"}

check_unstable_pairs(groupA_preferences, groupB_preferences, current_matching)
Out[3]:
[('M', 'A'), ('J', 'A')]
In [4]:
groupA_preferences = {
    "B": ["M", "N", "S", "K"],
    "H": ["K", "S", "M", "N"],
    "C": ["K", "M", "N", "S"],
    "E": ["S", "N", "M", "K"]
}

groupB_preferences = {
    "M": ["B", "H", "C", "E"],
    "K": ["H", "B", "C", "E"],
    "N": ["H", "C", "B", "E"],
    "S": ["C", "B", "H", "E"]
}

current_matching = {"B": "N", "H": "S", "C": "M", "E": "K"}

check_unstable_pairs(groupA_preferences, groupB_preferences, current_matching)
Out[4]:
[('B', 'M'), ('H', 'K'), ('C', 'K')]
In [5]:
import sys

sys.getrecursionlimit()  # 100-100的gale-shapley大概需要1500的recursion limit
# 如果要尝试>100的gale-shapley就需要把recursion limit调大
# sys.setrecursionlimit(4500)
Out[5]:
3000
In [6]:
groupA_preferences = {}
groupB_preferences = {}
current_matching = {}

groupA_ids = [f"A_{idx}" for idx in range(0, 100)]
groupB_ids = [f"B_{idx}" for idx in range(0, 100)]
for id_A in groupA_ids:
    groupA_preferences[id_A] = random.sample(groupB_ids, len(groupB_ids))
for id_B in groupB_ids:
    groupB_preferences[id_B] = random.sample(groupA_ids, len(groupA_ids))
groupB_ids_copy = deepcopy(groupB_ids)
for id_A in groupA_ids:
    random_B = random.choice(groupB_ids_copy)
    current_matching[id_A] = random_B
    groupB_ids_copy.remove(random_B)
print(f'Use random matching, there are {len(check_unstable_pairs(groupA_preferences, groupB_preferences, current_matching))} unstable matching pairs')
game = StableMarriage.create_from_dictionaries(
    groupA_preferences, groupB_preferences
)

game_matching = dict(game.solve(optimal="suitor"))
stable_matching = {}
for key, val in game_matching.items():
    stable_matching[str(key)] = str(val)

print(f'Use Gale-shapley algorithm, there are {len(check_unstable_pairs(groupA_preferences, groupB_preferences, stable_matching))} unstable matching pairs')

Use random matching, there are 2143 unstable matching pairs
Use Gale-shapley algorithm, there are 0 unstable matching pairs
In [13]: