成都麻將胡牌問題算法

2019-11-14 17:17:34

字體：大中小

來源：轉載

供稿：網友

題設：

* 成都麻將只能包括3種類型：筒（D），萬（W），條（T）。沒有“門、東南西北、紅中”。
* 每種牌都是數字從1到9，每個數字有4張，共36張。筒（D），萬（W），條（T）均一樣。
*
* 胡牌規則如下：
* 1、手里面的牌最多只有兩種類型，即必須打缺一種，不能出現：條，筒，萬都存在的情況。
* 2、必須有一個對子，即兩張相同的牌，比如：兩個2筒，兩個4條等。
* 3、剩余的牌，每3張需要湊成一個有效牌，比如：3個一樣的牌(3個2筒)，
* 或者3個順子(1條2條3條)，如果所有的牌都能夠湊好，再滿足規則2和1，有一個對子，并且所有的牌只有兩種類型，
* 那么就可以胡牌了。
* 4、有一種特殊牌，叫做七對，即全部的牌都是成對出現，比如:2筒2筒5筒5筒3筒3筒4條4條8條8條1條1條2條2條，
* 一共7對，再滿足條件1，也可以胡牌。
* 5、假設牌不會出現碰的情況，即手里面的牌肯定是14張。輸入數據肯定都是麻將牌，不用考慮異常輸入；也不用考慮會輸入“門”，“紅中”等成都麻將中不會出現的牌

要求：

* 輸入14張牌，判斷能不能胡牌。

* 例如：輸入：1D1D2D2D3D3D4W4W5W5W6W6W7W8W 輸出：False；輸入：1D1D1D3D3D3D4D5D6D7D8D9D4D4D 輸出：True

分析，建模：

0 以下的分析不包括7組對胡牌的情況，這種情況由于其特殊性，單獨處理。

1 關于牌面的關系，比較特殊的兩種情況是：相同，連續。用戶輸入的是字符，對于后一種關系的判斷不是很方便。怎么辦呢？很自然的就可以想到為每張牌面編碼，相鄰的牌面的編碼也連續。于是，我們很自然的想到，總共三種牌，每種從1到9，那么需要27個數就可以。于是假設‘D’的牌編號從0到9，‘W’的牌面編號從10到18，‘T’的牌面編號從19到27。按照這樣的編碼方式，如果手中的牌是1D1D1D，則對應的編號列表就是[1,1,1]；順子的編號就是[i, i+1, i+2]。

2 關于牌面組合的方法。因為要胡牌，所有的牌必須和其他的牌以某種關系組合，在牌面已經編碼的情況下，這種關系就是找到三張一樣的牌或者連續的三張牌。考慮，假設牌堆有牌i和i+2,而沒有i+1,那么i和i+2是不會發生任何聯系的，也就是說，牌面編碼上聯系或相同的牌才可能發生聯系。于是，可以先對手牌排序，我們以此從前向后來尋找這樣的關系，找到就剔除，繼續下去。如果最后所有的牌都能被剔除，則可以胡牌。比如說，某個階段，序列的前三個數值為[9,10,11]我們就可以認為他們是9D1W2W。。。等一下，好像出問題了。這種情況下。雖然數值上連續，但是實際上卻橫跨了兩個花色。對于這個問題，有兩種解決方法，第一種，就是在后期判斷時，以9n為界限，不許出現跨界配對，第二種，就是對我們的編碼規則稍作修改，仔細考慮會引起這個問題的原因是我們在編碼時只加入了對點數的考慮，沒有能區別花色的因素。為了讓不同花色的牌面不能配對，我們在編碼時加入間隔。最簡單的一種方法就是：‘D’的牌編號從1到9，‘W’的牌面編號從11到19，‘T’的牌面編號從21到29。以下是關于牌面編碼的代碼：

class SiChuanMaJiang(object):    pattern = ('D', 'W', 'T')    def __init__(self, pai):        self.pt   = p[1]        self.num  = int(p[0])        self.view = pai        self.id   = SiChuanMaJiang.pattern.index(self.pt)*10 + self.num #編碼，通過間隔一個數字，達到區別花色的目的

這樣，再后期檢索列表配對時，就不會出現跨花色配對的麻煩。

現在附上整個過程的代碼（沒有考慮7對出現的情況）：

  1 class SiChuanMaJiang(object):  2     pattern = ('D', 'W', 'T')  3   4     def __init__(self, pai):  5         self.pt   = p[1]  6         self.num  = int(p[0])  7         self.view = pai  8         self.id   = SiChuanMaJiang.pattern.index(self.pt)*10 + self.num  9  10 class InputParse(object): 11     @classmethod 12     def split_pai(cls, input): # 把字符串分開 13         result = [] 14         for i in range(0, 28, 2): 15             result.append(input[i:i+2]) 16         return result 17  18 class PaiAnaly(object): 19     def __init__(self): 20         self.total_num = 0 21         self.patterns = [] 22         self.id_list  = [] 23  24     def next_one(self, pai_instance): 25         if pai_instance.pt not in self.patterns: 26             self.patterns.append(pai_instance.pt) 27         self.id_list.append(pai_instance.id) 28         self.total_num += 1 29  30     @staticmethod 31     def qi_pai(pai_instance_list): # 對整個手牌進行統計 32         pai_mian = PaiAnaly() 33         map(lambda x: pai_mian.next_one(x), pai_instance_list) 34         return pai_mian 35  36     @staticmethod 37     def find_ok_three(sort_list): 38         if sort_list[0] == sort_list[1] and /  # 因為已經排序，所以直接找前三個是否相同，相同就返回 39                 sort_list[1] == sort_list[2]: 40             return sort_list[1], sort_list[2] 41         idx1 = 0 42         idx2 = 0 43         for i in range(1, len(sort_list)): # 尋找sort_list[0]+1 44             if sort_list[i] > sort_list[0] + 1: 45                 return False 46             if sort_list[i] == sort_list[0] + 1: 47                 idx1 = i 48                 break 49             if sort_list[i] == sort_list[0]: 50                 continue 51         if idx1 == 0: 52             return False 53  54         for j in range(idx1+1, len(sort_list)): # 在找到sort_list[0]+1的情況下，尋找sort_list[0]+2 55             if sort_list[j] > sort_list[idx1] + 1: 56                 return False 57             if sort_list[j] == sort_list[idx1] + 1: 58                 idx2 = j 59                 break 60             if sort_list[j] == sort_list[idx1]: 61                 continue 62         if idx2 == 0: 63             return False 64  65         return sort_list[idx1], sort_list[idx2] # 若找到，就返回。 66  67     @staticmethod 68     def recur_check(lt): # 遞歸過程 69         if len(lt) != 0: # 當列表為空，就認為可以胡牌 70             re = PaiAnaly.find_ok_three(lt)  71             if not re: 72                 return False 73             else: # 如果依然能夠配對，就去除已經配對的牌，繼續遞歸調用 74                 lt.remove(lt[0]) 75                 lt.remove(re[0]) 76                 lt.remove(re[1]) 77                 PRint lt 78                 return PaiAnaly.recur_check(lt)  79         else: 80             return True 81  82     def find_duizi(self): # 找出手牌中所有的對子，然后以每個對子作為頭，調用以上的遞歸過程 83         res = [] 84         for i in range(13): 85             try: 86                 # print self.id_list[i] 87                 if self.id_list[i] == self.id_list[i+1] and / 88                         self.id_list[i] != self.id_list[res[-1]]: 89                     res.append(i) 90             except IndexError: 91                 res.append(i) 92         print res 93         return res 94  95  96     def judge_hui(self): 97         self.id_list.sort() 98         if self.total_num != 14: 99             return False100         if len(self.patterns) == 3:101             return False102 103         duizi_index = self.find_duizi()104         print '本來牌面: %s' % self.id_list105 106         for idx in duizi_index:107             tl = copy.deepcopy(self.id_list)108             print '對子: %s%s' % (tl[idx], tl[idx+1])109             val = tl[idx]110             tl.remove(val)111             tl.remove(val)112             print '去除對子以后的牌面: %s' % tl113             r =  PaiAnaly.recur_check(tl)114             if not r:115                 continue116             else:117                 '-------------'118                 return True119 120 if __name__ == '__main__':121     pai_string = raw_input('牌面:')122     pai_list = InputParse.split_pai(pai_string)123     pai_instance_list = []124     for p in pai_list:125         pai_instance_list.append(SiChuanMaJiang(p))126 127     pai_ready = PaiAnaly.qi_pai(pai_instance_list)128     r = pai_ready.judge_hui()129 130     if r:131         print '胡了'132     else:133         print '不能胡'

以上的代碼看似沒有問題，其實，任然有一點不足：

在find_ok_three方法中，我們找到三張一樣就返回，沒有尋找是不是還存在順子的情況，舉個例子：假設此時列表中的前5張牌為[1,1,1,2,3,...]，那么這個時候，我們的程序會返回對牌1,1,1，然后程序會把這些數刪除，繼續遞歸過程。而另一方面，如果，我們先刪除1,2,3然后再遞歸，那么這兩次遞歸的結果會不會有什么不一樣呢。再進一步說，優先刪除對牌，進行遞歸，會不會造成誤判，即：是否本來可以判定胡牌的牌面，因為優先刪除對牌的策略，導致判定為不能胡牌。

現在，我們假設，優先刪除對牌不會造成誤判，即證明：

"""優先選擇去除三個一樣的算法是對結果無害的。"""

證明過程：
# 能去除3個，只有兩種情況：前三個一樣或者前四個一樣。
# (1) 若前三個一樣。假設為a，則序列為[a, a, a, a+1,...]
#      則胡牌可能為{[a, a, a], 其他序列...},或者{[a, a+1, a+2], [a, a+1, a+2], [a, a+1, a+2], ...},
#      可以看到，在第二種情況下，a+1，a+2 也至少有3個，
#      分類討論：
# (A) a+1 個數= 3 & a+2 個數 >= 3
#          這時按照優先去除三個一樣的做法，會依次去除三個a+1, 三個a+2,則剩余的牌的數量和第二種一致，這時候，判定結果只取決于最后三張牌，顯然無影響。

#
# (B) a+1 個數= 4 & a+2 個數>= 3
# 這時會先去除三個a+1, 剩余一個a+1,必然配對{a+1, a+2, a+3}, 又有a+2的張數大于等于3，所以若此時想配對，只有可能是[a+2, a+2, a+2]
# 這種情況下的能胡牌的牌面是固定的[a, a, a, a+1, a+1, a+1, a+1, a+2, a+2, a+2, a+2, a+3]，算法判定胡牌，不會出錯。

# (2) 若前四個一樣。假設為a，則序列為[a, a, a, a, a+1,...]
#      則胡牌可能為{[a, a, a], [...]},或者{[a, a+1, a+2], [a, a+1, a+2], [a, a+1, a+2], [a, a+1, a+2]},
#      可以看到，在第二種情況下,只有一種情況能胡牌：a, a+1，a+2 各有4個，
#      按照優先去除三個一樣的算法，依次做下去，會依次去除[a, a, a], [a, a+1, a+2], [a+1, a+1, a+1], [a+2, a+2, a+2]，判定胡牌，不會出錯。
#
#  綜上，優先去除三個一樣的做法一定能得到正確答案，若改進題目為求所有可能的胡法，則需要分叉處理。

上一篇：Python函數信息

下一篇：Python學習（七）面向對象——繼承和多態