"""CS386 Assignment 8 starter. Marriage instances: men_prefs / women_prefs are dicts person -> list of acceptable people on the other side, most preferred first. A matching is a dict containing both m -> w and w -> m for every matched pair (unmatched people are absent). Roommates instances: prefs is a dict person -> list of acceptable others.""" from builtins import NotImplementedError import itertools, random # ------------------------------------------------------------ to implement def deferred_acceptance(men_prefs, women_prefs, count=False): """Men-proposing DA in O(L) time. Return mu (or (mu, number_of_proposals) if count).""" raise NotImplementedError def blocking_pair(men_prefs, women_prefs, mu): """Return a blocking pair (m, w) or None if mu is stable. O(L) time.""" raise NotImplementedError def college_admissions(student_prefs, college_prefs, cap): """Student-proposing DA with capacities. Return dict student -> college (absent if unassigned).""" raise NotImplementedError def cloned_instance(student_prefs, college_prefs, cap): """Return (men_prefs, women_prefs) of the cloned one-to-one market (Problem 6a).""" raise NotImplementedError def roommates(prefs): """Irving's algorithm. Return a stable matching (dict) or None.""" raise NotImplementedError # ------------------------------------------------------------ provided def is_stable(men_prefs, women_prefs, mu): return blocking_pair(men_prefs, women_prefs, mu) is None def brute_force_stable(men_prefs, women_prefs): """All stable matchings (exponential; use only for n <= 6).""" men = list(men_prefs) res = [] def rec(i, mu, used): if i == len(men): if is_stable(men_prefs, women_prefs, mu): res.append(dict(mu)) return m = men[i] rec(i + 1, mu, used) # m unmatched for w in men_prefs[m]: if w not in used and m in women_prefs[w]: mu[m] = w; mu[w] = m; used.add(w) rec(i + 1, mu, used) del mu[m], mu[w]; used.discard(w) rec(0, {}, set()) return res def random_instance(n, complete=True, p=0.7, seed=None): rng = random.Random(seed) M = [f"m{i}" for i in range(n)]; W = [f"w{i}" for i in range(n)] acc = {(m, w) for m in M for w in W if complete or rng.random() < p} mp = {m: [w for w in W if (m, w) in acc] for m in M} wp = {w: [m for m in M if (m, w) in acc] for w in W} for L in list(mp.values()) + list(wp.values()): rng.shuffle(L) return mp, wp def roommates_brute_force(prefs): """All stable matchings for roommates, n <= 8.""" people = list(prefs) rk = {x: {y: i for i, y in enumerate(L)} for x, L in prefs.items()} res = [] def stable(mu): for x in people: for y in prefs[x]: if x in rk[y] and mu.get(x) != y: if (x not in mu or rk[x][y] < rk[x][mu[x]]) and (y not in mu or rk[y][x] < rk[y][mu[y]]): return False return True def rec(i, mu): while i < len(people) and people[i] in mu: i += 1 if i == len(people): if stable(mu): res.append(dict(mu)) return x = people[i] rec(i + 1, mu) for y in prefs[x]: if y not in mu and x in rk[y] and y != x: mu[x] = y; mu[y] = x rec(i + 1, mu) del mu[x], mu[y] rec(0, {}) return res