参考 九条可怜 大佬的 利用查表法求麻将向听数。过程中有一些数学证明省略了,在这里记录一下加深理解。说句题外话,大佬在知乎唯二的两篇文章,最新的一篇 大数快速取模魔法,和我当时做的关于伽罗华域(Galois Field, GF)的毕设简直不要太贴合。哎,我真是学艺不精。
原文主要是针对向听数计算和序列生成进行讲解的,本文主题亦如此。
0x01 向听数计算
对于大众麻将,包括日本麻将和国标麻将,不考虑特殊牌型(七对、十三幺、不靠等)基本的胡牌条件为:m 个面子加上 1 个对子,即可胡牌。为行文方便,将胡牌公式简单记为
3m+2
其中 3 代表面子,2 代表对子。结合麻将规则,容易知道对于能够胡牌的手牌总数 N,有
N \in \{2, 5, 8, 11, 14\}
牌效率理论定义了向听数(Syanten),指一副牌距离听牌状态最少还差几次打摸动作。0 向听 = 听牌,-1 向听 = 胡牌。若非特殊说明,下文所指的向听数皆为一般牌型的向听数。
对两张不同的牌 x, y 定义距离计算函数 D(x,y):
D(x,y) = \begin{cases}
0, (x, y 为同种牌)\\
1, (x, y 为同种数牌,且数字差 = 1) \\
2, (x, y 为同种数牌,且数字差 = 2) \\
\infty, (otherwise) \\
\end{cases}
根据 3m + 2 ,将牌组序列 tiles 分为两个部分:要凑成若干个面子的部分 tiles_{m},\ \sum tiles_{m}\ mod\ 3=0 和要凑成一对对子的部分 tiles_{p},\ \sum tiles_{p}=2。定义向听数计算函数 S(tiles)。