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

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

     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 後就只會往下一個排名的對象求婚，不會再往回向曾經求婚過的對象求婚了>

* **偽代碼**

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

    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

    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})$