---
# System prepended metadata

title: Stable Marriage Problem
tags: [algorithms]

---

# Stable Marriage Problem
(Gale Shapley Algorithm)
###### tags: `algorithms`

* **題目描述**
給定兩組同樣大小的集合A和B，集合A對集合B各成員有一個喜好程度排序，同樣地集合B對集合A各成員也有一個喜好程度排序，要輸出一個穩定且完美的配對組合，也就是必須符合
--> 完美: 每個集合A成員"恰好"配對到一個集合B的成員，換句話說大家都會有一個且只有一個配對的對象
--> 穩定: 不會出現任何沒被配在一起的a(集合A的成員)和b(集合B的成員)喜歡對方勝過自己被配對的結果(否則該兩人有外遇的可能)，也就是不會出現以下的狀況
![](https://i.imgur.com/nWMevGt.png)
```
     m 和 w 配在一起
     m' 和 w' 配在一起
     但 m 和 w' 更喜歡對方勝過自己的配對對象
```

* **特性**
A-optimal & B-pessimal

* **演算法描述**
  集合A的成員一開始都是 free man，依照喜好程度(先從最喜歡的開始)向集合B的成員求婚，集合B的成員只能選擇 accept 或 reject，如果 accept 則雙方進入 engage 階段，但此狀態隨時可以更改，一旦集合B的成員遇到他更喜歡的對象向他求婚，就會把現有的 engage 對象 reject 掉，此時被 reject 掉的對象恢復 free man 身分並按照他的喜好程度表向下一個排名的對象求婚，直到沒有free man
  <附註: 集合A的成員被 reject 後就只會往下一個排名的對象求婚，不會再往回向曾經求婚過的對象求婚了> 

* **偽代碼**

``` java
1. initialize each person to be free
2. while (some man m is free and hasn't proposed to every woman)do
3.     w = highest ranked woman in m's list to whom has not yet proposed
4.    if (w is free) then
5.        (m,w) become engaged
6.    else if (w prefers m to her fiance m') then
7.        (m,w) become engaged
8.        m' become free
9. return the set S of engaged pairs
```
* **好的資料結構**
    各成員用數字編號(ID)取代名字來記錄
    * 集合A資料(ID): array
    * A對B的喜好程度表(prefrence list): array (索引為排名，內容為B成員的ID編號)
    * Next list: array, 記錄a下次要求婚的對象排名，初始為1(不論被 accept 還是 reject)
    * free man: linked list，動態資料記錄當下的free man(因為 linked list 的 insert 和 delete 複雜度都是 O(1))
    * 集合B資料(ID): array
    * B對A的喜好程度表(prefrence list): array (索引為排名，內容為A成員的ID編號)
    * current list: array, 記錄b當前 engage 的對象ID，初始為0表示沒有人
    * ranking list: 記錄b對集合A的排名，也就是索引為集合A成員的數字編號，內容為其在b心目中的排名，跟prefrence list相反
    --> 如此可讓複雜度降到 $O(n^{2})$
    
* **輸入範例**
    * 集合A(男生)對集合B(女生)喜好程度表
        
    |        |   1    |   2    |   3    |   4    |   5    |
    |--------|--------|--------|--------|--------|--------|
    | Victor | Bertha | Amy    | Diane  | Erika  | Clare  |
    | Wyatt  | Diane  | Bertha | Amy    | Clare  | Erika  |
    | Xavier | Bertha | Erika  | Clare  | Diane  | Amy    |
    | Yancey | Amy    | Diane  | Clare  | Bertha | Erika  |
    | Zeus   | Bertha | Diane  | Amy    | Erika  | Clare  |
    
    --> 轉換成數字編號得下表(省略最上面那列)
    --> Victor編號1，Wyatt編號2，Xavier編號3，Yancey編號4，Zeus編號5
    --> Amy編號1，Bertha編號2，Clare編號3，Diane編號4，Erika編號5
    ```java
    1 2 1 4 5 3
    2 4 2 1 3 5
    3 2 5 3 4 1
    4 1 4 3 2 5
    5 2 4 1 5 3
    ```
    
    * 集合B(女生)對集合A(男生)喜好程度表
    
    |        |   1    |   2    |   3    |   4    |   5    |
    |--------|--------|--------|--------|--------|--------|
    | Amy    | Zeus   | Victor | Wyatt  | Yancey | Xavier |
    | Bertha | Xavier | Wyatt  | Yancey | Victor | Zeus   |
    | Clare  | Wyatt  | Xavier | Yancey | Zeus   | Victor |
    | Diane  | Victor | Zeus   | Yancey | Xavier | Wyatt  |
    | Erika  | Yancey | Wyatt  | Zeus   | Xavier | Victor |
    
    --> 轉換成數字編號得下表(省略最上面那列)
    --> Victor編號1，Wyatt編號2，Xavier編號3，Yancey編號4，Zeus編號5
    --> Amy編號1，Bertha編號2，Clare編號3，Diane編號4，Erika編號5
    ```java
    1 5 1 2 4 3
    2 3 2 4 1 5
    3 2 3 4 5 1
    4 1 5 4 3 2
    5 4 2 5 3 1
    ```
    
* **程式**
    * [Github](https://github.com/Gemini064/Algorithm/tree/master/StableMarriage)
* **複雜度**
    * step 1: 初始化 --> $O(n)$
    * step 2~8: 配對 --> 搭配好的資料結構可達 $O(n^{2})$
    * step 9: 回傳值 --> $O(n)$
    * 依據 **[複雜度符號](https://hackmd.io/fqdlbUYtRuGg9wakUJCXOQ)** 的 "加法原則"，該演算法的複雜度為 $O(n^{2})$
    