参考链接:
http://hp.vector.co.jp/authors/VA046927/mjscore/mjalgorism.html
http://hp.vector.co.jp/authors/VA046927/mjscore/AgariIndex.java
http://hp.vector.co.jp/authors/VA046927/mjscore/AgariBacktrack.java
核心思想:
9张万,9张条,9张饼,4张风,3张箭,一共34种牌。
那么34种牌就至少需要6bit才能够全部保存得下。(1 2 4 8 16 32 64 …)
麻将的手牌有14张,14张 * 6bit = 84bit
麻将的所有组合大约有1700万种,所以需要的内存为 84bit * 1700万 = 175MB 左右。
所以需要进行优化:
例如:
222456万345678饼北北,可以编码为30111011111102(三张相同牌,三张连续牌,六张连续牌,两张相同牌,中间隔开)。
下一步是将其二进制化,采用如下特制规则:
1→0
2→110
3→11110
4→1111110
10→10
20→1110
30→111110
40→11111110
很容易看出,这样编码后每张牌只占用1到2位空间,最恶情况子下(十四张不连单牌)仅占用27位。跟之前的84位相比,单组数据压缩了三分之二以上。更牛逼的是,和牌表从1700万种具体组合下降到仅仅9362种形状排列!
下面给出几个二进制化的例子
需要倒过来看,对照上面的规则从右往左看:
2 –> 0x7 –> 0111
23 –> 0xFB –> 1111 1011
32 –> 0xEF –> 1110 1111
233 –> 0x1F7B –> 0001 1111 0111 1011
2303 –> 0x3EFB –> 0011 1110 1111 1011
21110330 –> 0x1F7A3 –> 0001 1111 0111 1010 0011