A stable roommate problem with 4 students a, b, c, d is defined as follows. Each student ranks the other three in strict order of preference. A match- 1 2. ing is defined as the separation of the students into two disjoint pairs. A matching is stable if no two separated students prefer each other to their current roommates. Does a stable matchin…

rma.py

# -*- coding: utf-8 -*-
from itertools import combinations, permutations, product


def matching(stu_pre):
    m = {}
    s = {}
    already_matched = []
    not_match_pairs = []
    match = []

    for x in combinations(stu_pre.keys(), 2):
        m[x] = stu_pre[x[0]].index(x[1]) + stu_pre[x[1]].index(x[0])

    for k, v in m.items():
        if v not in s.keys():
            s[v] = []
        s[v].append(k)

    for k in sorted(s.keys()):
        for pair in s[k]:
            if pair[0] not in already_matched and pair[1] not in already_matched:
                match.append(pair)
                already_matched.append(pair[0])
                already_matched.append(pair[1])
            else:
                not_match_pairs.append(pair)
    for x in not_match_pairs:
        if stu_pre[x[0]].index(x[1]) + stu_pre[x[1]].index(x[0]) == 0:
            raise TypeError("Found it")


def preference_generator(student_list):
    r_data = {}
    for ec_s in student_list:
        r_data[ec_s] = []
        for x in permutations(student_list, 3):
            if ec_s not in x:
                r_data[ec_s].append(x)
    return r_data


if __name__ == '__main__':
    students = [1, 2, 3, 4]
    p_list = preference_generator(students)

    pp_list = {}
    for x in list(product(p_list[1], p_list[2], p_list[3], p_list[4])):
        pp_list[1] = x[0]
        pp_list[2] = x[1]
        pp_list[3] = x[2]
        pp_list[4] = x[3]
        matching(pp_list)

    print "If this program run successful and it did not raise exception, the answer is YES"