時間：20210928

背景：有個相親活動，需要暗地里給男女進行匹配，畢竟明面上直接說不喜歡哪個異性總是尷尬的，匹配的話，方法眾多，并不能讓每個人都滿意，根據各自的意向，總能計算整體意向都不錯的，

太長了不看，直接操作：

線下讓N對男女：

1. 寫個小紙條，各自給N個異性排序，更喜歡的排在前面
2. 得到：
   1. 女生的選擇：womanChoices
      1. 女1：男2，男5，男1，....
      2. 女2：...
      3. ...
      4. 女N：...
   2. 男生的選擇：manChoices
      1. 同理

操作：

1. 進入網站：代碼在線運行 - 在線工具
2. 選擇python
   1. 不要用python3
3. 代碼復制進去
4. 修改代碼里的兩個變數：womanChoices、manChoices
   1. 將之前線下統計得到的，放在對應位置
   2. 

5. 點擊“執行Run”
6. 右側出結果即可

演算法：GS演算法（蓋爾-沙普利演算法（Gale-Shapley algorithm））

演算法思想：略

演算法偽代碼：

樣例解釋：

1、1對男女，不考慮

2、兩對男女，分別優秀男1、一般男2；優秀女1、一般女2（“優秀”、“普通”方便理解，換成“青菜”、“蘿卜”一個意思）

1.0、優秀女、男互相看中，普通女、男互相看中

• 女1喜歡：男1>男2
• 女2喜歡：男2>男1
• 男1喜歡：女1>女2
• 男2喜歡：女2>女1
• 結果：男1——女1、男2——女2分別匹配
• 解釋：蘿卜青菜各有所愛，分別各自找到自己最中意的

2.1.1、兩女爭優秀男，兩男爭優秀女

• 女1喜歡：男1>男2
• 女2喜歡：男1>男2
• 男1喜歡：女1>女2
• 男2喜歡：女1>女2
• 結果：優秀男1——優秀女1、一般男2——一般女2
• 解釋：優者則優

2.2.1、兩女爭優秀男，兩男爭普通女

• 女1喜歡：男1>男2
• 女2喜歡：男1>男2
• 男1喜歡：女2>女1
• 男2喜歡：女2>女1
• 結果：優秀男1——普通女2、普通男2——優秀女1
• 解釋：
  • 兩男爭普通女，該普通女不普通，優先級高，是個“優秀女”，優秀男1同理，故兩個被相爭的在一起
  • 該情況和上面一種“兩女爭優秀男，兩男爭優秀女”是類似

2.1.2、兩女爭普通男，兩男爭普通女：換身份，轉換為“兩女爭優秀男，兩男爭優秀女”情況一樣，

2.2.2、兩女爭普通男，兩男爭優質女：換身份，轉換為“兩女爭優秀男，兩男爭普通女”情況一樣

3.1.1、兩女爭優秀男，優秀男爭優秀女、普通男爭普通女

• 女1喜歡：男1>男2
• 女2喜歡：男1>男2
• 男1喜歡：女1>女2
• 男2喜歡：女2>女1
• 結果：優秀男1——優秀女1、一般男2——一般女2
• 解釋：普通男1沒被優秀女1優先選，

3.2.1、兩女爭優秀男，優秀男爭普通女、普通男爭優秀女

• 結果：優秀男1——普通女2、普通男2——優秀女1
• 解釋：和3.1.1情況類似，優秀男權重更高（被兩女相爭）

3.1.2、兩女爭普通男，普通男爭優秀女、優秀男爭普通女

• 解釋：和3.1.1情況類似，普通男、優秀男身份互換即可

3.2.2、兩女爭普通男，普通男爭普通女、優秀男爭優秀女

• 解釋：和3.2.1情況類似，普通男、優秀男身份互換；

4、四角戀：女1->男1->女2->男2->女1

• 女1喜歡：男1>男2
• 女2喜歡：男2>男1
• 男1喜歡：女2>女1
• 男2喜歡：女1>女2
• 結果：
  • 女士優先時：女1——男1、女2——男2
  • 男士優先時：女2——男1、女1——男2

代碼：

# coding:utf-8
"""
Demo of Gale-Shapley stable marriage algorithm.

Usage is:
   python marriage.py  [menfile]  [womenfile]

or

   python marriage.py  [menfile]  [womenfile]  V

for verbose mode.

For simplicity, the file format is assumed (without checking) to match
the following format:

  bob:     alice,carol
  david:   carol,alice

and likewise for the womenfile, where there should be precisely same
number of men as with women, and the identifiers should be
self-consistent between the two files.
"""
import sys

# 原作者的例子:
womanChoices = '''
W:       D,B,C,A
X:       D,B,A,C
Y:       A,D,B,C
Z:       B,A,D,C
'''
manChoices = '''
A:      W,X,Z,Y
B:      W,Y,Z,X
C:      X,W,Y,Z
D:      W,Z,X,Y
'''

# 1.0、優秀女、男互相看中，普通女、男互相看中
womanChoices = '''
女1：男1，男2
女2：男2，男1
'''
manChoices = '''
男1：女1，女2
男2：女2，女1
'''

# 2.1.1、兩優秀女爭兩優秀男、兩優秀男爭兩優秀女
womanChoices = '''
女1：男1，男2
女2：男1，男2
'''
manChoices = '''
男1：女1，女2
男2：女1，女2
'''

# 3.1.1、兩女爭優秀男，優秀男爭優秀女、普通男爭普通女
womanChoices = '''
女1：男1，男2
女2：男1，男2
'''
manChoices = '''
男1：女1，女2
男2：女2，女1
'''

# 4、四角戀：女1->男1->女2->男2->女1
womanChoices = '''
女1：男1，男2
女2：男2，男1
'''
manChoices = '''
男1：女2，女1
男2：女1，女2
'''
# ---------------------------------------------------------------------------------------
# 現場活動男女們的選擇：（格式類似上面的，一人一行，冒號、逗號注意）
# 女生
womanChoices = '''

'''

# 男生選擇的結果：放這里
manChoices = '''

'''
# ---------------------------------------------------------------------------------------

class Person:
    """
    Represent a generic person
    """

    def __init__(self, name, priorities):
        """
        name is a string which uniquely identifies this person

        priorities is a list of strings which specifies a ranking of all
          potential partners, from best to worst
        """
        self.name = name
        self.priorities = priorities
        self.partner = None

    def __repr__(self):
        return 'Name is ' + self.name + '\n' + \
               'Partner is currently ' + str(self.partner) + '\n' + \
               'priority list is ' + str(self.priorities)


class Man(Person):
    """
    Represents a man
    """

    def __init__(self, name, priorities):
        """
        name is a string which uniquely identifies this person

        priorities is a list of strings which specifies a ranking of all
          potential partners, from best to worst
        """
        Person.__init__(self, name, priorities)
        self.proposalIndex = 0                   # next person in our list to whom we might propose

    def nextProposal(self):
        goal = self.priorities[self.proposalIndex]
        self.proposalIndex += 1
        return goal

    def __repr__(self):
        return Person.__repr__(self) + '\n' + \
            'next proposal would be to ' + self.priorities[self.proposalIndex]


class Woman(Person):
    """
    Represents a woman
    """

    def __init__(self, name, priorities):
        """
        name is a string which uniquely identifies this person

        priorities is a list of strings which specifies a ranking of all
          potential partners, from best to worst
        """
        Person.__init__(self, name, priorities)

        # now compute a reverse lookup for efficient candidate rating
        self.ranking = {}
        for rank in range(len(priorities)):
            self.ranking[priorities[rank]] = rank

    def evaluateProposal(self, suitor):
        """
        Evaluates a proposal, though does not enact it.

        suitor is the string identifier for the man who is proposing

        returns True if proposal should be accepted, False otherwise
        """
        return self.partner == None or self.ranking[suitor] < self.ranking[self.partner]


def parseFileOld(filename):
    """
    Returns a list of (name,priority) pairs.
    """
    people = []
    f = file(filename)
    for line in f:
        pieces = line.split(':')
        name = pieces[0].strip()
        if name:
            priorities = pieces[1].strip().split(',')
            for i in range(len(priorities)):
                priorities[i] = priorities[i].strip()
            people.append((name, priorities))
    f.close()
    return people


def parseFile(choices):
    choices = choices.replace('：', ':')
    choices = choices.replace('，', ',')
    people = []
    for line in choices.split('\n'):
        pieces = line.split(':')
        name = pieces[0].strip()
        if name:
            priorities = pieces[1].strip().split(',')
            for i in range(len(priorities)):
                priorities[i] = priorities[i].strip()
            people.append((name, priorities))
    return people


def printPairings(men):
    for man in men.values():
        print man.name, 'is paired with', str(man.partner)


def main_old():
    verbose = len(sys.argv) > 3

    # initialize dictionary of men
    menlist = parseFile(sys.argv[1])
    men = dict()
    for person in menlist:
        men[person[0]] = Man(person[0], person[1])
    unwedMen = men.keys()

    # initialize dictionary of women
    womenlist = parseFile(sys.argv[2])
    women = dict()
    for person in womenlist:
        women[person[0]] = Woman(person[0], person[1])

    ############################### the real algorithm ##################################
    while unwedMen:
        m = men[unwedMen[0]]             # pick arbitrary unwed man
        w = women[m.nextProposal()]      # identify highest-rank woman to which
        #    m has not yet proposed
        if verbose:
            print m.name, 'proposes to', w.name

        if w.evaluateProposal(m.name):
            if verbose:
                print '  ', w.name, 'accepts the proposal'

            if w.partner:
                # previous partner is getting dumped
                mOld = men[w.partner]
                mOld.partner = None
                unwedMen.append(mOld.name)

            unwedMen.remove(m.name)
            w.partner = m.name
            m.partner = w.name
        else:
            if verbose:
                print '  ', w.name, 'rejects the proposal'

        if verbose:
            print "Tentative Pairings are as follows:"
            printPairings(men)
            print

    # we should be done
    print "Final Pairings are as follows:"
    printPairings(men)


def main(manChoices, WomanChoices):
    # initialize dictionary of men
    menlist = parseFile(manChoices)
    men = dict()
    for person in menlist:
        men[person[0]] = Man(person[0], person[1])
    unwedMen = men.keys()

    # initialize dictionary of women
    womenlist = parseFile(WomanChoices)
    women = dict()
    for person in womenlist:
        women[person[0]] = Woman(person[0], person[1])

    ############################### the real algorithm ##################################
    while unwedMen:
        m = men[unwedMen[0]]             # pick arbitrary unwed man
        w = women[m.nextProposal()]      # identify highest-rank woman to which
        #    m has not yet proposed
        if w.evaluateProposal(m.name):
            if w.partner:
                # previous partner is getting dumped
                mOld = men[w.partner]
                mOld.partner = None
                unwedMen.append(mOld.name)

            unwedMen.remove(m.name)
            w.partner = m.name
            m.partner = w.name
    #####################################################################################

    # we should be done
    print "Final Pairings are as follows:"
    printPairings(men)


if __name__ == "__main__":
    # 女士優先，womanChoices放前面, 否則放后面
    main(womanChoices, manChoices)

作者源代碼：

• Gale-Shapley Stable Marriage Algorithm

參考資料：

• [演算法]Gale-Shapley Algorithm-穩定匹配演算法的設計、實作與探討
• 演算法 | 蓋爾-沙普利(Gale-Shapley)婚姻穩定匹配演算法
• Gale-Shapley演算法（基于python3.6）