Funkce programu · Stabilní párování preferencí

from collections import deque
def stable_pairs(proposers, receivers):
    if type(proposers) not in (list, tuple) or type(receivers) not in (list, tuple):
        raise ValueError("preference tables must be lists or tuples")
    n = len(proposers)
    if n > 20 or len(receivers) != n: raise ValueError("equal sizes up to 20")
    for rows in (proposers, receivers):
        for row in rows:
            if type(row) not in (list, tuple) or len(row) != n or any(type(v) is not int for v in row) or set(row) != set(range(n)):
                raise ValueError("complete strict preferences")
    ranks = [{v:i for i,v in enumerate(row)} for row in receivers]
    free, next_choice = deque(range(n)), [0]*n
    owner, partner = [None]*n, [None]*n
    while free:
        p = free.popleft()
        r = proposers[p][next_choice[p]]
        next_choice[p] += 1
        old = owner[r]
        if old is None or ranks[r][p] < ranks[r][old]:
            owner[r], partner[p] = p, r
            if old is not None: partner[old] = None; free.append(old)
        else: free.append(p)
    return partner