由光棍节想到的算法问题。假设一个学校里有100个少年和100个少女，少年和少女心中都有一个好感度数值排列表，现在我们来做CP(coterie partner)，按照正常的剧情展开，勇敢的少年们去向少女们告白，大致流程是这样：

第一天，所有少年都去找排在他们好感度列表第1位的少女表白。告白结束后，少女如果只收到一个少年的告白，那么就和这个少年交往。如果收到多于一个少年的告白，就和其中她最喜欢的少年交往，把其他少年都拒绝掉。

第二天，所有在第一天被发好人卡的少年们，接着发起告白行动，去向排在自己好感度列表第2位的少女告白。告白结束后，如果某个少女已经在交往中，但是又有一个她更喜欢的少年来向她告白，那少女就把原来那个少年甩掉，再和这个她更喜欢的少年交往。

第三天，少年们继续发起告白运动，包括第一天告白成功，但第二天被挖了墙角的，接着向还没有拒绝过他的女生中他最喜欢的那个告白。

如此直到CP结束，我们可以得到一个稳定的CP，稳定的概念是，对于任何一对恋爱关系——比如少年A和少女A——都不存在少年A对少女B的好感度大于少女A，或是少女B对于少年A的好感度大于她现任的男朋友少年B的情况。以上就是1962年美国数学家戴维·戈尔（David Gale）和劳埃德·夏普利（Lloyd Shapley）对稳定婚姻问题研究出的Gale & Shapley算法了。经过计算发现，这种情况看似少女们拥有自主选择权，真正收益的其实是勇往直前的少年们，他们总能追到自己好感度列表中相当靠前的少女。当然，这个算法最主要是解决诸如学生对于其意向学校的选择，座位的安排，这类问题的实际可行性。

Algorithm[Python]

前面的描述有点复杂，先将其简化，假设有三男三女，互相好感度如下：

guyprefers = {
 'kyou':    ['haruhi', 'yuki', 'mikuru'],
 'itsukl':  ['haruhi', 'mikuru', 'yuki'],
 'shamisen':['mikuru', 'yuki', 'haruhi']}
galprefers = {
 'haruhi': ['kyou', 'itsukl', 'shamisen'],
 'yuki':   ['shamisen', 'kyou', 'itsukl'],
 'mikuru': ['kyou', 'itsukl', 'shamisen']}
#顺手从dict中先取得少年和少女的名字列表，之后会用到
guys = sorted(guyprefers.keys())
gals = sorted(galprefers.keys())

接下来按照前面的流程，开始CP

guyprefers2 = copy.deepcopy(guyprefers)
galprefers2 = copy.deepcopy(galprefers)
engaged = {}

guysfree = guys #少年们还没有告白，都是单身
while guysfree:
    guy = guysfree.pop(0)#取出第一个少年
    guyslist = guyprefers2[guy]#取得少年的好感度list
    gal = guyslist.pop(0)#取出第一个少女
    fiance = engaged.get(gal)
    if not fiance:#如果取不到值，则是单身
        engaged[gal] = guy #接受少年的告白 
        print("  %s and %s" % (guy, gal))
    else:
        # 算法的核心，比较少年在少女们心中的好感度排名
        galslist = galprefers2[gal]
# 如果来告白的少年好感度高于现任男友，则抛弃掉现任男友
        if galslist.index(fiance) > galslist.index(guy):
            engaged[gal] = guy
            print("  %s dumped %s for %s" % (gal, fiance, guy))
            if guyprefers2[fiance]:
                guysfree.append(fiance)#被抛弃的少年进入单身列表
# 如果来告白的少年好感度低于现任男友，则发卡拒绝
        else:
            guysfree.append(guy)#被发卡的少年进入单身列表
    guysfree.append(guy)

Coding & Run Result

import copy

guyprefers = {
 'kyou':    ['haruhi', 'yuki', 'mikuru'],
 'itsukl':  ['haruhi', 'mikuru', 'yuki'],
 'shamisen':['mikuru', 'yuki', 'haruhi']}
galprefers = {
 'haruhi': ['kyou', 'itsukl', 'shamisen'],
 'yuki':   ['shamisen', 'kyou', 'itsukl'],
 'mikuru': ['kyou', 'itsukl', 'shamisen']}

guys = guyprefers.keys()
gals = galprefers.keys()

 
def cp():
    guysfree = guys
    engaged  = {}
    guyprefers2 = copy.deepcopy(guyprefers)
    galprefers2 = copy.deepcopy(galprefers)
    while guysfree:
        guy = guysfree.pop(0)
        guyslist = guyprefers2[guy]
        gal = guyslist.pop(0)
        fiance = engaged.get(gal)
        if not fiance:
            engaged[gal] = guy
            print("  %s and %s" % (guy, gal))
        else:
            galslist = galprefers2[gal]
            if galslist.index(fiance) > galslist.index(guy):
                engaged[gal] = guy
                print("  %s dumped %s for %s" % (gal, fiance, guy))
                if guyprefers2[fiance]:
                    guysfree.append(fiance)
            else:
                guysfree.append(guy)
    return engaged

print('\nEngagements:')
engaged = cp()

print('\nCouples:')
print('  ' + ',\n  '.join('%s is engaged to %s' % couple
                          for couple in sorted(engaged.items())))

运行结果：