Stable Matching
(misc/stable_matching.hpp)

• View this file on GitHub
• Last update: 2024-01-08 00:27:17+09:00
• Include: #include "misc/stable_matching.hpp"

Description

(男性最適) 安定マッチングを返す．

$n$ 人の男性と $n$ 人の女性がいる状況を考える．各人は異性に対して選好順序を持っている．このとき，安定マッチングとは，$n$ 組の男女のマッチングであって，互いに現在組んでいる相手よりもお互いのことが好きであるような男女のペア (ブロッキングペア) が存在しないようなものである．

どの男性も安定マッチングでペアになれる女性のうち，もっとも好きな女性とペアになっているような安定マッチングを男性最適安定マッチングと言う．男性最適安定マッチングは Gale-Shapley アルゴリズムによって $O(n^2)$ 時間で求めることができる．

Operations

• vector<int> stable_matching(vector<vector<int>> man, vector<vector<int>> woman)
  • 男性と女性の各人の選好順序が与えられたとき，(男性最適) 安定マッチングの1つにおいて，各女性と婚約している男性を返す．
  • 時間計算量: $O(n^2)$

Reference

• Stable marriage problem - Wikipedia
• Gale-Shapley algorithm - Wikipedia

Code

#pragma once
#include <stack>
#include <vector>

std::vector<int> stable_matching(const std::vector<std::vector<int>>& man,
                                 const std::vector<std::vector<int>>& woman) {
    const int n = man.size();
    // the smaller the better
    std::vector preference(n, std::vector<int>(n));
    for (int j = 0; j < n; ++j) {
        for (int k = 0; k < n; ++k) {
            preference[j][woman[j][k]] = k;
        }
    }
    std::vector<int> idx(n);
    std::vector<int> engaged(n, -1);
    std::stack<int> st;
    for (int i = 0; i < n; ++i) st.push(i);
    while (!st.empty()) {
        int i = st.top(), j = man[i][idx[i]++];
        if (engaged[j] == -1 || preference[j][i] < preference[j][engaged[j]]) {
            st.pop();
            if (engaged[j] != -1) st.push(engaged[j]);
            engaged[j] = i;
        }
    }
    return engaged;
}

#line 2 "misc/stable_matching.hpp"
#include <stack>
#include <vector>

std::vector<int> stable_matching(const std::vector<std::vector<int>>& man,
                                 const std::vector<std::vector<int>>& woman) {
    const int n = man.size();
    // the smaller the better
    std::vector preference(n, std::vector<int>(n));
    for (int j = 0; j < n; ++j) {
        for (int k = 0; k < n; ++k) {
            preference[j][woman[j][k]] = k;
        }
    }
    std::vector<int> idx(n);
    std::vector<int> engaged(n, -1);
    std::stack<int> st;
    for (int i = 0; i < n; ++i) st.push(i);
    while (!st.empty()) {
        int i = st.top(), j = man[i][idx[i]++];
        if (engaged[j] == -1 || preference[j][i] < preference[j][engaged[j]]) {
            st.pop();
            if (engaged[j] != -1) st.push(engaged[j]);
            engaged[j] = i;
        }
    }
    return engaged;
}

Back to top page