序

最近业余时间在研究排列组合的相关问题,话题涉及到了在不考虑花色的情况下？54张牌按照斗地主的方式以20，17，17的方式分给3个人有多少中可能解决方案？
我觉得这个问题有点意思，并以sql脚本的形式实现了问题的求解过程，希望大家能从这篇文章中所有收获。

问题分析

以4个3为例，分给地主1，农民2，农民3的所有组合情况如下：

既4个3在3个玩家中的可能情况有15种。在不考虑斗地主手牌数限制的情况下,因A到K有13张牌，则A到K的所有位置的组合数有$15^{13}$种可能性。
以大王为例,分给地主1，农民2，农民3的所有组合情况如下：

在不考虑斗地主手牌数限制的情况下,大王和小王在三家的可能性有3*3=9种可能性。
所以牌型组合的理论上限是$9*15^{13}$。接近于$1.75*10^{16}$。

根据计数原理,结合上图可知：
如果37在玩家1，2，3的手牌张数分别是20，0，0的可行方法是1种。
如果8Q在玩家1，2，3的手牌张数分别是0，17，3的可行方法是35种。
如果K到大王在玩家1，2，3的手牌张数分别是0，0，14的可行方法是1种。
所以三个步骤组合起来的总可行方法是$1*35*1=35$种方法。

具体细节参考Sql server版斗地主牌型组合统计的代码,最终的出来的结果是138712181744994,即$1.3871*10^{14}$。即在不区分花色的情况下，斗地主所有的牌型组合数。

总结

记录斗地主的所有牌型这种方式来做AI是不切实际的，毕竟普通PC机是没有办法存储$1.3871*10^{14}$条数据的。

参考资料

• 计数原理
• m个球放到n个箱子中几种解法
• 欢乐斗地主出牌方式统计

序

在集合S取出n个元素其和为K个数统计这篇文章中提到了笛卡尔积的这种解法，但是以笛卡尔积的方式求解的时候，我中午点击运行，我晚上回来的时候才输出了168条牌型组合，然后一直没有响应，后来粗略估算了一下，需要在1.44E+18条左右数据中进行筛选，而选出总手牌数为20条相当于大海捞针，所以需要重新对问题进行思考。
先将问题明确定义——“在N张手牌中，可能的出牌方式有多少种？”

牌型分析

以地主20张手牌为例,20张手牌可能1个炸弹也没有，最多有5个炸弹。所以20张手牌,炸弹的取值范围的取值范围是[0,5];
而3张相同的牌带1张单牌也是四张牌,所以20张手牌，出三张相同的牌带一张单牌的次数也是[0,5];
如果手牌中存在66667777这样的四张牌,6667和7776这种打法和一个6炸和7炸是两种打牌的方式。
同样就算是以6,6,6,6,7,7,7,7这样的8张单牌一次打出去，欺负下家或上家手里只有3,4,5了也不是不可以。
所以66667777这样8张牌在不考虑输赢的情况下也是有很多种打法的。而巧的是，我们讨论的是不考虑输赢的情况。

20张手牌有几种打出去的方式呢？

最多以20次单牌的形式打出去。
最多以10次对子的形式打出去。
最多以3次三连对的形式打出去。
依次类推，有了以下的表格：

具体实现

请下载C#版源代码,放到对应的控制台去执行即可。
这里列举几个示例结果：
手牌数为1

1
2
3

手牌数为1时,可能的打法情况为:
1:  牌型为：单张,每次消耗1,出了1次,共消耗掉1张牌
所有牌型列举完成

手牌数为2

1
2
3
4
5

手牌数为2时,可能的打法情况为:
1:  牌型为：王炸,每次消耗2,出了1次,共消耗掉2张牌
2:  牌型为：对子,每次消耗2,出了1次,共消耗掉2张牌
3:  牌型为：单张,每次消耗1,出了2次,共消耗掉2张牌
所有牌型列举完成

手牌数为3

1
2
3
4
5
6

手牌数为3时,可能的打法情况为:
1:  牌型为：3张牌,每次消耗3,出了1次,共消耗掉3张牌
2:  牌型为：单张,每次消耗1,出了1次,共消耗掉1张牌    牌型为：王炸,每次消耗2,出了1次,共消耗掉2张牌
3:  牌型为：单张,每次消耗1,出了1次,共消耗掉1张牌    牌型为：对子,每次消耗2,出了1次,共消耗掉2张牌
4:  牌型为：单张,每次消耗1,出了3次,共消耗掉3张牌
所有牌型列举完成

手牌数为4

1
2
3
4
5
6
7
8
9
10

手牌数为4时,可能的打法情况为:
1:  牌型为：炸弹,每次消耗4,出了1次,共消耗掉4张牌
2:  牌型为：3张牌带1张,每次消耗4,出了1次,共消耗掉4张牌
3:  牌型为：对子,每次消耗2,出了1次,共消耗掉2张牌    牌型为：王炸,每次消耗2,出了1次,共消耗掉2张牌
4:  牌型为：对子,每次消耗2,出了2次,共消耗掉4张牌
5:  牌型为：单张,每次消耗1,出了1次,共消耗掉1张牌    牌型为：3张牌,每次消耗3,出了1次,共消耗掉3张牌
6:  牌型为：单张,每次消耗1,出了2次,共消耗掉2张牌    牌型为：王炸,每次消耗2,出了1次,共消耗掉2张牌
7:  牌型为：单张,每次消耗1,出了2次,共消耗掉2张牌    牌型为：对子,每次消耗2,出了1次,共消耗掉2张牌
8:  牌型为：单张,每次消耗1,出了4次,共消耗掉4张牌
所有牌型列举完成

根据以上结果中的示例2和示例5可知，就算是7778也可以以777和8分两次打出去。
手牌数为5

1
2
3
4
5
6
7
8
9
10
11
12
13
14

手牌数为5时,可能的打法情况为:
1:  牌型为：5张牌的顺子,每次消耗5,出了1次,共消耗掉5张牌
2:  牌型为：3张牌带1对,每次消耗5,出了1次,共消耗掉5张牌
3:  牌型为：3张牌,每次消耗3,出了1次,共消耗掉3张牌    牌型为：王炸,每次消耗2,出了1次,共消耗掉2张牌
4:  牌型为：对子,每次消耗2,出了1次,共消耗掉2张牌    牌型为：3张牌,每次消耗3,出了1次,共消耗掉3张牌
5:  牌型为：单张,每次消耗1,出了1次,共消耗掉1张牌    牌型为：炸弹,每次消耗4,出了1次,共消耗掉4张牌
6:  牌型为：单张,每次消耗1,出了1次,共消耗掉1张牌    牌型为：3张牌带1张,每次消耗4,出了1次,共消耗掉4张牌
7:  牌型为：单张,每次消耗1,出了1次,共消耗掉1张牌    牌型为：对子,每次消耗2,出了1次,共消耗掉2张牌    牌型为：王炸,每次消耗2,出了1次,共消耗掉2张牌
8:  牌型为：单张,每次消耗1,出了1次,共消耗掉1张牌    牌型为：对子,每次消耗2,出了2次,共消耗掉4张牌
9:  牌型为：单张,每次消耗1,出了2次,共消耗掉2张牌    牌型为：3张牌,每次消耗3,出了1次,共消耗掉3张牌
10:  牌型为：单张,每次消耗1,出了3次,共消耗掉3张牌    牌型为：王炸,每次消耗2,出了1次,共消耗掉2张牌
11:  牌型为：单张,每次消耗1,出了3次,共消耗掉3张牌    牌型为：对子,每次消耗2,出了1次,共消耗掉2张牌
12:  牌型为：单张,每次消耗1,出了5次,共消耗掉5张牌
所有牌型列举完成

限于篇幅，不再一一列举，根据程序列举出来的可能性如下图所示:

可知有17张手牌时,可以有1729种出牌方式。
可知有20张手牌时,可以有4815种出牌方式。
也许基于此，就有了赌徒说搏一搏，单车变摩托的说法。

注意,20张手牌的出牌方式并不能达到4815种，一个12张牌的顺子是12张牌,而再来两个炸弹8张牌，加起来也是20张牌。但是去掉3~A的12张牌，只能算出”2222”一个炸弹了。即”12张牌的顺子和2个炸弹”虽说符合代码的逻辑，但是并不符合现实中的牌型。换句话说，参考资料中的代码并没有考虑这种情况。

问题是还有哪些牌型组合在一起能满足总手牌数，但是不符合现实中的牌型呢？

总结

本以为在计算{1,2,3,4}中取出任意个数，与取出顺序无关时使用笛卡尔积的方式是很好的方式；结果在该问题中待处理数据竟达到了1.44E+18(1.44乘以10的18次方)条之多。
由此可知，问题并不是想当然就能够得到解决的，实践永远是检验真理的标准。
如果在每种牌型设置其对应的权重,所以在AI中的斗地主，如果能检测出手牌是10连对,或333444555666777带789JQ类型,得赶紧明牌不是么？

参考资料

• 集合S取出n个元素其和为K个数统计
• C#版源代码
• 牌型组合excel
• m个球放到n个箱子中几种解法