程式員的算法趣題Q09: 落單的男女

目錄

1. 問題描述

2. 解題分析

3. 代碼及測試

4. 思考

1. 問題描述

        人們聚集在某個活動會場上，根據到場順序排成一排等待入場，活動的主辦人員，想把人們從隊列的某個位置分成兩組，想要讓分開的兩組裡至少有一組（原題是每一組）的男女人數都均等。但如果到場順序不對，可能出現無論怎麼分，兩組都不能出現男女均等的情況。

        舉個例子，有3位男性、3位女性以“男男女男女女”的順序到達，如圖所示，無論從隊列的哪個位置分開，兩組的男女人數都不均等。但如果到場的順序為“男男女女男女”，那麼隻需要在第4個人處分組就可以令分開的兩組男女人數均等了。

        求男性20人、女性10人的情況下，有多少種到場順序會導緻無論怎麼分組都沒有任何一組的組内男女人數能夠均等？（原書中表述的有問題，因為如果要求兩組中男女人數都相等，男女總人數就必然相等。而本題題設就是男女人數不等，這樣無論按什麼順序到來都滿足條件，過于trivial的問題）。

2. 解題分析

        按照動态規劃的思路進行子問題分解。

        令男女人數分别為M(Male)和F(Female)，令目前已經到達的男生和女生人數分别為m和f。記這種情況下接下來滿足題設要求的人員到來順序數為g(m,n)。

        接下來要麼來男生，要麼來女生：

        (1) 如果來男生的話，則問題變成了子問題g(m+1,f)

        (2) 如果來女生的話，則問題變成了子問題g(m,f+1)

        是以可以得到遞推關系式：

        接下來要确定邊界條件。

        Case1: 如果在某個時刻，到達的男生人數m和女生人數f相等，就相當于找到一個可以“均等分割”的情況（不符合題設且無需繼續搜尋），是以應該傳回0。但是需要注意的是，必須在m>0的條件下以上論斷才有效，否則的話，一開始就是m=n=0的情況，這個沒有意義。

        Case2: 如果在某個時刻，尚未到達的男生人數M-m和尚未到達的女生人數F-f相等，也就相當于找到一個可以“均等分割”的情況（不符合題設且無需繼續搜尋），是以應該傳回0。同樣需要注意要在(M-m)>0的條件下以上論斷才有效。

        Case3: 前兩種情況都是屬于搜尋失敗的情況，接下來确定搜尋成功的情況。第一感是男生已經到齊而還沒有碰到可以平均分割，或者女生已經到齊而還沒有碰到可以平均分割，都是屬于找不到“均等分割”的情況。但是這裡有漏洞。比方說，M=20,F=10,女生已經到達10人，男生隻到了9人，此時雖然尚未滿足“均等分割”，但是接下來再來一個男生就湊出“均等分割”了。所有還得在以上條件的基礎上加上一個限制條件，即任一方（記為A方）已經到齊而另一方（（記為B方））到達的人數也不少于A方時，此時沒有到達“均等分割”條件，後續隻有B方人員到來，就不可能會再出現“均等分割”的情況了。

        以下用遞歸+memoization的方式實作（無它，就是這個代碼寫起來簡單，哪怕效率低一些也值得^-^）.

3. 代碼及測試

# -*- coding: utf-8 -*-
"""
Created on Sun Aug 29 07:14:15 2021

@author: chenxy
"""

import sys
import time
import datetime
# import random
from   typing import List
# from   queue import Queue
# from   collections import deque

class Solution:
    
    def noEqualPartition(self, M:int, F:int) -> int:
        """
        :M:     The number of boys
        :F:     The number of girls
        :ret:   The number of incoming order for no-equal-partition.
        """               
                
        memo = dict()
        # Recursion core: 
        # Return the number of incoming orders which would satisfy the condition, 
        # when the number of already arrived boys and girls are m and f respectively
        def recursion(m,f):        
            # print('m,f=',m,f)

            if (m,f) in memo:
                return memo[(m,f)]
                
            if (m==f) and m>0:
                memo[(m,f)] = 0
                return 0
            if (M-m)==(F-f) and (M-m)>0 : # Found equal partition
                memo[(m,f)] = 0
                return 0
            if (M==m and f>=m) or (F==f and (m>=f)):
                memo[(m,f)] = 1
                return 1

            
            sum = 0
            if M-m >= 1:
                sum += recursion(m+1,f)
            if F-f >= 1:
                sum += recursion(m,f+1)
            memo[(m,f)] = sum
            return sum
        
        return recursion(0,0)
           

if __name__ == '__main__':        
            
    sln    = Solution()    

    M      = 20
    F      = 10
    tStart = time.time()
    ans    = sln.noEqualPartition(M,F)
    tCost  = time.time() - tStart
    print('M,F={0},{1}, ans={2}, tCost={3:6.3f}(sec)'.format(M,F,ans,tCost)) 
           

        運作結果：

                M,F=20,10, ans=2417416, tCost= 0.000(sec)

4. 思考

        以上解題過程中其實是磕磕碰碰的，就是說一開始有些細節沒有完全想到，導緻結果不完全一緻。然後可能要經過多次修正才能得到最終正确的答案。這是在已經知道答案的條件下可以這樣做。如果沒有現成的正确答案呢？那如何來判斷吭哧吭哧得到的解答是正确的呢？這個可能是每一個人多多少少都會碰到的問題。有些問題在規模很小的比較容易用紙和筆計算出答案用于程式測試驗證，但是并不總是有這麼happy的情況，這種情況下怎麼辦呢？

        另外原書以及其它部落格中提到最多的估計就是最短路徑解法了。。。這個後面再回頭補充，先把每一道題都過一遍要緊。

       上一篇：Q08: 優秀的機器人

        下一篇：Q10: 輪盤的最大值

        本系列總目錄參見：程式員的算法趣題：詳細分析和Python全解