歡迎光臨
每天分享高質量文章

面對喜歡的人,是該表白還是等TA來撩?這個演算法給你答案

導讀:本文生動地討論了穩定匹配問題蓋爾沙普利演算法的Python實現。該演算法是穩定匹配模型的著名解法。

關鍵詞:穩定匹配 蓋爾-沙普利演算法 求婚 Python


p.s. 文末有原始碼分享

作者:城市資料團木木

來源:資料團學社(ID:metrodata_xuexi)

秋天到了,又是吃螃蟹的季節。白富美學姐前兩天約我吃最愛的大閘蟹,席間向來開心的她卻顯得心事重重。

“你腫麽啦?”我仔細地掰開蟹殼,問道。

“十一假期好多朋友辦婚禮,可我男票一點要求婚的意思都沒有,我都想考慮備胎了。”

“你自己和他說嘛!”我放下了金黃的大閘蟹。

“我可是個妹子,這樣多不好。”學姐嘆了口氣。

看著學姐猶猶豫豫的樣子就知道她需要鼓勵了~我眉頭一皺,計上心來:

學姐呀,我來給你講個故事~

01

有一座城市,當地風俗是,想結婚的男子必須先向心儀的女子求婚,而女子則需要等待求婚。

牧師每年會邀請人數相同的適婚男女參與一次集體相親。一次相親活動可能有很多輪,男子會首先向自己最愛的女子求婚,女子則會在所有的追求者中選擇她的最愛;如果男子被拒絕,下一輪會向他第二喜歡的女子求婚;上一輪已經訂婚的女子如果得到她更愛的人的求婚,則會毫不留情地拋棄未婚夫,和更愛的人在一起。被拋棄的男子需要重新參與求婚。

如此反覆,等大家都訂婚,就舉辦集體婚禮。

假設:

1)參加求婚的男女數量保持一致

2)每個男子都按喜愛程度對女子進行排序,比如最愛a,其次愛b,再次愛c

3)每個女子也同樣給每個男子排序


*此方法名為Gale-Shapley演算法。優點如下:

1. 總有大家都訂了婚的一天,不可能無限迴圈

2. 中止後所有的婚姻是穩定婚姻

(不穩定婚姻:比如有兩對夫婦M1&F1;和M2&F2;, M1的老婆是F1,但他更愛F2;而F2的老公雖說是M2,但她更愛M1。這樣的婚姻就是不穩定婚姻)

有興趣的讀者可以自行搜索證明過程。

02

學姐的眼睛開始放光了:

坐在家裡等求婚,下輩子請讓我生在這個城市吧!

我神秘一笑:

是不是女孩子的天堂,讓我們用Python來看一看最後的匹配滿意度吧!

(此處展示部分代碼,完整源檔案請看文末)

1. 樣本生成

為了完成模擬過程,我們首先需要一些樣本,即隨機生成數量相等(可設置數量)的男性和女性,同時生成他們對每個異性個體的喜愛排名

#設置男女生喜好樣本
print('==============================生成樣本資料==============================')
man = pd.DataFrame( [['w'+str(i) for i in random.sample(range(1,women_num+1),women_num)] \
                      for i in range(man_num)],
                    index = ['m'+str(i) for i in range(1,man_num+1)],
                    columns = ['level'+str(i) for i in range(1,women_num+1)]
                    )

women = pd.DataFrame( [['m'+str(i) for i in random.sample(range(1,man_num+1),man_num)] \
                      for i in range(women_num)],
                    index = ['w'+str(i) for i in range(1,women_num+1)],
                    columns = ['level'+str(i) for i in range(1,man_num+1)]
                    )
return (man,women)

2. 模擬男性求婚過程

每天上午,每位還沒訂婚的男子,會向還沒拒絕過他的女子中,他最愛的那一個求婚。

print('==============================測試集{}模擬開始=============================='.format(i))
print('==============================開始模擬求婚過程==============================')
level_num = 0
while man_ismapping['love_level'].min() == 0:
    level_num += 1
    print('==============================開始第{}天婚姻配對=============================='.format(level_num))
    u_mapping_man = man_ismapping[man_ismapping.target == 'n'].index.tolist()

    if level_num 2:
        level_col = 'level' + str(level_num)
        man_choose = man[man.index.isin(u_mapping_man)][level_col].to_frame().reset_index()
        man_choose.columns = ['man_id''women_id']
        man_choose['range'] = 1
    else:
        m_id = u_mapping_man
        l = []
        for man_id in m_id:
            col_n = int(man_ismapping[man_ismapping.index == man_id].range[0])
            level_col = 'level' + str(col_n + 1)
            women_id = man[man.index == man_id][level_col][0]
            rg = col_n + 1
            l.append([man_id, women_id, rg])
        man_choose = pd.DataFrame(l, columns=['man_id''women_id''range'])

3. 模擬女性接受訂婚的過程

每天下午,每位女性會在自己接到的求婚信中,選擇她最中意的男子接受求婚;如果沒接到求婚,就繼續等待。

for r in range(0, len(man_choose)):
    relationship = man_choose[man_choose.index == r]
    m = [i for i in relationship['man_id']][0]
    w = [i for i in relationship['women_id']][0]
    find = women[women.index == w].unstack().reset_index()
    find.columns = ['level''women_id''man_id']
    find = int([i for i in find[find['man_id'] == m]['level']][0].split('level')[1])
    o_love_level = [i for i in women_ismapping[women_ismapping.index == w]['love_level']][0]
    rg = [i for i in relationship['range']][0]
    if o_love_level == 0:
        women_ismapping.loc[w, 'love_level'] = find
        women_ismapping.loc[w, 'target'] = m
        women_ismapping.loc[w, 'range'] = level_num
        man_ismapping.loc[m, 'love_level'] = rg
        man_ismapping.loc[m, 'target'] = w
        man_ismapping.loc[m, 'range'] = rg
    elif o_love_level > find:
        m_o = women_ismapping.loc[w, 'target']
        man_ismapping.loc[m_o, 'love_level'] = 0
        man_ismapping.loc[m_o, 'target'] = 'n'
        man_ismapping.loc[m, 'love_level'] = rg
        man_ismapping.loc[m, 'target'] = w
        man_ismapping.loc[m, 'range'] = rg
        women_ismapping.loc[w, 'love_level'] = find
        women_ismapping.loc[w, 'target'] = m
        women_ismapping.loc[w, 'range'] = level_num
    else:
        man_ismapping.loc[m, 'range'] = rg
        pass


4. 運行代碼,並匯出結果

03

學姐看著正在運行模擬過程有點著急了,我抽取其中一輪的結果先展示給她看:

▲縱軸代表該次模擬結果中,某位男性/女性的伴侶喜愛排名,即:匹配到的伴侶是他/她第X喜歡的異性

顯然,男性匹配到的伴侶離自己的最愛比女性更近——不止一點點!這可和“妹子天堂”的預期有點遠啊!

學姐陷入了困惑:明明女性才掌握著訂婚的決定權,而且男性即使暫時訂婚成功,也有被拋棄的可能啊!你看,隨著匹配輪次增加,男性的伴侶總是從自己最喜歡的物件慢慢變成不那麼喜歡的物件而女性伴侶卻在一步步變好。你這個會不會是偶然啊!

我:是不是偶然,讓我們來看看100次模擬中,男性/女性匹配到的伴侶喜愛排名均值分佈吧~

▲縱軸代表其中一次模擬中,男性/女性的平均伴侶喜愛排名均值,即:匹配到的伴侶是他們/她們第X喜歡的異性

可以明顯看到,男性最終匹配到的伴侶的喜愛排名普遍高於女性。

學姐終於收起了質疑:原來主動出擊真有這麼大的作用!為什麼呀~

我分析道:學姐你看,女孩只能坐在家裡等求婚,她喜歡的人可能連看到她的機會都沒有。而男性在主動做出選擇之時,每次都能選擇自己最喜歡的物件。即使被拒絕,他的下一次求婚,也能送給可能接受他的、他最愛的女孩兒。這個游戲保證男孩的伴侶是可能和他在一起的最好的那一個,但對女孩就不是

學姐:你說得對。面對自己喜歡的人,我應該去爭取,而不只是等待。

我:這就對啦!世界上有什麼事不需要努力呢?你有喜歡的人,就要好好努力,提升自己,去吸引ta,愛ta~

在大資料公眾號後臺對話框回覆表白即可獲取文中原始碼和G-S演算法有關資料!

據統計,99%的大咖都完成了這個神操作


更多精彩


在公眾號後臺對話框輸入以下關鍵詞

查看更多優質內容!


PPT | 報告 | 讀書 | 書單

Python | 機器學習 | 深度學習 | 神經網絡

區塊鏈 | 揭秘 | 乾貨 | 數學

猜你想看

Q: 你要主動出擊了嗎

歡迎留言與大家分享

覺得不錯,請把這篇文章分享給你的朋友

轉載 / 投稿請聯繫:baiyu@hzbook.com

更多精彩,請在後臺點擊“歷史文章”查看

赞(0)

分享創造快樂