Stable matching
(matching/stable_matching.hpp)

View this file on GitHub
Last update: 2022-12-03 14:13:47+00:00
Include: #include "matching/stable_matching.hpp"

It solves stable matching problem using the Gale-Shapley algorithm. The algorithm results in a perfect matching and a stable matching. For given sets $A$ and $B$ the result is $A$-optimal and $B$-pessimal. It assumes that $\lvert A \rvert = \lvert B \rvert = n$.

stable_matching

std::vector<int> stable_matching(const std::vector<std::vector<int>> &a,
                                 const std::vector<std::vector<int>> &b);

Parameters

a, b
$a$ is an $n \times n$ 2D vector. $a[i]$ is a permutation of $0, 1, \cdots, n-1$. For $0 \le j \lt k \lt n$, $i$ prefers $a[i][j]$ over $a[i][k]$, where $i$ is in set $A$ and $a[i][j]$ and $a[i][k]$ are in set $B$. For $b$ it’s vice versa.

Return value

It returns a vector $r$ of length $n$, such that $i$ in set $A$ and $r[i]$ in set $B$ are matched.

Complexity

$\mathcal{O}\left(n^2\right)$

Problems

References

Verified with

test/stable_matching.stress.test.cpp

Code

#ifndef STABLE_MATCHING_HPP
#define STABLE_MATCHING_HPP

#include <numeric>
#include <vector>

std::vector<int> stable_matching(const std::vector<std::vector<int>> &a,
                                 const std::vector<std::vector<int>> &b) {
    const auto n = static_cast<int>(a.size());
    std::vector<std::vector<int>> b_priority(n, std::vector<int>(n));
    for (auto i = 0; i < n; ++i) {
        for (auto j = 0; j < n; ++j) {
            b_priority[i][b[i][j]] = j;
        }
    }
    std::vector<int> a_propose(n), b_match(n, -1), unmatched(n);
    std::iota(unmatched.begin(), unmatched.end(), 0);
    while (!unmatched.empty()) {
        const auto l = unmatched.back();
        unmatched.pop_back();
        const auto r = a[l][a_propose[l]];
        if (b_match[r] == -1) {
            b_match[r] = l;
        } else if (b_priority[r][l] < b_priority[r][b_match[r]]) {
            ++a_propose[b_match[r]];
            unmatched.push_back(b_match[r]);
            b_match[r] = l;
        } else {
            ++a_propose[l];
            unmatched.push_back(l);
        }
    }
    std::vector<int> a_match(n);
    for (auto i = 0; i < n; ++i) {
        a_match[b_match[i]] = i;
    }
    return a_match;
}

#endif // STABLE_MATCHING_HPP

#line 1 "matching/stable_matching.hpp"



#include <numeric>
#include <vector>

std::vector<int> stable_matching(const std::vector<std::vector<int>> &a,
                                 const std::vector<std::vector<int>> &b) {
    const auto n = static_cast<int>(a.size());
    std::vector<std::vector<int>> b_priority(n, std::vector<int>(n));
    for (auto i = 0; i < n; ++i) {
        for (auto j = 0; j < n; ++j) {
            b_priority[i][b[i][j]] = j;
        }
    }
    std::vector<int> a_propose(n), b_match(n, -1), unmatched(n);
    std::iota(unmatched.begin(), unmatched.end(), 0);
    while (!unmatched.empty()) {
        const auto l = unmatched.back();
        unmatched.pop_back();
        const auto r = a[l][a_propose[l]];
        if (b_match[r] == -1) {
            b_match[r] = l;
        } else if (b_priority[r][l] < b_priority[r][b_match[r]]) {
            ++a_propose[b_match[r]];
            unmatched.push_back(b_match[r]);
            b_match[r] = l;
        } else {
            ++a_propose[l];
            unmatched.push_back(l);
        }
    }
    std::vector<int> a_match(n);
    for (auto i = 0; i < n; ++i) {
        a_match[b_match[i]] = i;
    }
    return a_match;
}

Stable matching (matching/stable_matching.hpp)