成都麻将胡牌有关问题算法

成都麻将胡牌问题算法

题设：

* 成都麻将只能包括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 False
100         if len(self.patterns) == 3:
101             return False
102 
103         duizi_index = self.find_duizi()
104         print '本来牌面: %s' % self.id_list
105 
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' % tl
113             r =  PaiAnaly.recur_check(tl)
114             if not r:
115                 continue
116             else:
117                 '-------------'
118                 return True
119 
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]，判定胡牌，不会出错。
#
#  综上，优先去除三个一样的做法一定能得到正确答案，若改进题目为求所有可能的胡法，则需要分叉处理。

成都麻将胡牌有关问题算法

相关推荐