日麻向听数计算
两年前对日麻比较狂热的时候自己整理的笔记了，现在已经很久没碰日麻了。整理自己电脑上资料的时候看到了这个，就发出来吧。笔记可能写的也不完整，也不打算再补充什么了。
手牌向听数计算
一、加算法
手牌最少还需要摸到多少张有效牌才能听牌，这个牌数就是向听数。
二、减算法（http://www9.plala.or.jp/majan/fst13.html）
1、一般形向听数
向听数=8-2×面子数-面子候补数
或：
向听数=2×待做面子数-面子候补数
注意：
（1）面子候补数=搭子数+对子数。
（2）对面子、搭子和对子进行计数时，不能有重复使用的牌，即同一枚牌不能同时出现在不同的面子或面子候补中。
（3）面子数+面子候补数不超过4。如果面子+面子候补数>4，那么只需要取出其中的（4-面子数）个面子候补，因此我们需要将上面式子中面子候补数的值修改为（4-面子数）。（例如：1245m567p1235689s的向听数为8-2×2-2=2）
（4）如果取出的面子及面子候补以外的牌中还存在可以作为雀头的对子，那么还需要在上式计算结果的基础上将向听数减1。（例如：1245m567p1235688s的向听数为1）
（5）如果取出面子候补时有可能在未使用的牌中保留可以作为雀头的对子，那么就尽量那样进行提取，因为这样做的话可以使向听数最小化。（例如：2356m34788p34s123z应当取23m、56m、34p、34s为面子候补）
（6）有多个对子可以提取为雀头的时候，尽量保证取出雀头后面子候补数最多，更准确地说应该是使取出雀头后（2×面子数+面子候补数）的值最大化，也就是说采用取出雀头后向听数最小化的取法。（例如：2356m3446p123445z应当取44z为雀头）
（7）将手牌拆解为面子和面子候补时，一般都是先尽量多取出面子，在剩下的部分尽量多取出面子候补，但是也有例外。这种情况下，应该采用使得（2×面子数+面子候补数）的值最大化，也就是使得向听数最小化的取法。（例如：13334555712345z应当取345m、13m、35m、57m为面子和面子候补，而非取333m、555m为面子）
（8）拆取面子和面子候补时的程序化步骤：
For 每个雀头候补：
假设其为雀头
先取出雀头
递归取出面子和面子候补，向听数=8-2×面子数-面子候补数-1
找出最小的向听数
End
假设没有雀头
递归取出面子和面子候补，向听数=8-2×面子数-面子候补数
找出最小的向听数
（9）仍然存在例外的情况。例如“东东东东南南南南西西西北北北”的向听数计算为0，而实际上应当为1，又如“东东东东南南南南西西西西北北”的向听数计算为1，而实际上应当为2。这种情况的出现是因为持有4枚相同的字牌。要解决这种情况，首先需要对孤立牌和是否持有4枚相同的字牌进行统计。如果孤立牌全为第4枚的字牌，那么就需要将向听数增加1。
（10）上面的计算公式仅适用于1、4、7、10、13枚手牌的向听数计算。2、5、8、11、14枚牌时的向听数，可以看作：切掉一枚牌做成的1、4、7、10、13枚手牌的最小向听数。正常情况下，手牌的枚数不可能变成0、3、6、9、12枚，因此暂不考虑这些枚数的牌形的向听数。
2、国士无双向听数
首先数一数幺九牌（一九字牌）的种类数，从13中减去这个种类数，如果存在幺九牌的对子，就再减1，最后得到的就是国士无双的向听数。
国士无双向听数=13-幺九牌种类数-(幺九对子数?1:0)
3、七对子向听数
一般情况下：
七对子向听数=6-对子数
但是手牌中有4枚相同的牌时，由于牌的种类数不足7，所以会导致向听数增加。最终，七对子向听数的计算公式为：
七对子向听数=6-对子数+(牌的种类数<7?7-牌的种类数:0)
注意：
（1）暗刻或未杠的暗杠算作也仅算作1个对子。
三、查表法求向听数
（一）牌的编码
如：“一一一二三五六④⑤⑧99东南”，牌要先排好序，可以按mpsz的顺序，数牌数字从小到大，字牌按东→南→西→北→白→发→中的顺序排序。
1、牌的数量的编码（计数）
结果如下：
{"一":3, "二":1, "三":1, "五":1, "六":1, "④":1, "⑤":1, "⑧":1, "9":2, "东":1, "南":1}
也就是：31111111211
2、牌的距离的编码（间距编码）
参考mjscore和了形判定的编码方法：
间隔为1，即相差为2的两枚同色数牌中间补1个0
间隔为2或以上，即相差为3或以上的两枚同色数牌之间，不同种牌之间补2个0
向听数计算与和了判定中不一样的地方是，和了判定中数牌只有连续与否有意义，间隔为1或以上没有区别，而在向听数计算中，如35也是有效的听牌形，所以间隔为1的两枚同色数牌也有单独区别的意义，而间隔为2或以上没有区别。
如上，结果为：3110110011001002001001
以此编码方式，最长的手牌及其编码结果为：
“一四七②⑤⑧369东西南北中”：1001001001001001001001001001001001001001
共3×13+1=40位，每一位数值用3bit的话，需要3×40=120bit
3、编码转换（节省存储空间）
利用0不会连续3个这一点，应用下面的转换规则：
我想到了两种对应方式，分别考虑两种规则的效率。
规则① 规则②
1→10 1→0
2→110 2→1110
3→1110 3→1111110
4→11110 4→1111111110
10→100 10→10
20→1100 20→11110
30→11100 30→11111110
40→111100 40→11111111110
100→1000 100→110
200→11000 200→111110
300→111000 300→111111110
400→1111000 400→111111111110
也就是说，牌的数量按如下对应：
规则① 规则②
1→1 1→空
2→11 2→111
3→111 3→111111
4→1111 4→111111111
规则①补充：后面没有0，补上0，后面有1个0，补上00，后面有2个0，补上000
规则②补充：后面没有0，补上0，后面有1个0，补上10，后面有2个0，补上110
规则①的另一种对应方式：
0→0
1→10
2→110
3→1110
4→11110
在两种规则下，手牌对应的编码结果为：
规则①：
“一二三四五六①②③④⑤东东东”：1111110011111003
→101010101010001010101010001110
“一一一二三五六④⑤⑧99东南”：3110110011001002001001
→111010100101000101000100011000100010
“一四七②⑤⑧369东西南北中”：
1001001001001001001001001001001001001001
→100010001000100010001000100010001000100010001000100010，
共4×13+2=54位，需要54bit的存储空间。
规则②：
“一二三四五六①②③④⑤东东东”：1111110011111003
→000001100000110111111
“一一一二三五六④⑤⑧99东南”：3110110011001002001001
→3，1，10，1，100，1，100，100，200，100，1
→1111110，0，10，0，110，0，110，110，111110，110，0
→1111110010011001101101111101100
“一四七②⑤⑧369东西南北中”：
1001001001001001001001001001001001001001
→1101101101101101101101101101101101101100，
共3×13+1=40位，需要40bit的存储空间。
使用C++中的bitset数据结构，可以有效节省内存空间。并且bitset支持二进制数的位操作，如按位与&、按位或|、按位异或^、按位取反~、左移<<、右移>>等位运算以及这些位运算的复合赋值操作。此外，还可以通过[]对bitset中的元素进行访问和赋值（类似数组，最低位下标为0）。
（其它bitset数据结构的函数方法可以参考如下网址：
http://www.cplusplus.com/reference/bitset/bitset/）
由此可见，规则②在对应极端情况下的编码所需的存储空间更小。规则①实际上被编码结果没有连续4个0限制住了，虽然在一些特殊情况下需要的存储空间相比规则②更少，但在极端情况下需要更多的存储空间，而由于存储一个牌形需要的存储空间取决于极端情况，所以这导致了存储空间的浪费。综上，我们采用规则②的对应方式。
4、调查所有的编码序列（枚举）
①对数量的枚举：即对枚数N的加法分解问题，分解的结果类似步骤1的结果。
②对距离的枚举：
限制条件：
Ⅰ）以步骤2的结果来枚举，由00分割的各个子序列的距离<=8（1到9的距离），各个子序列的距离总和<=8×3=27。
Ⅱ）数牌的子序列之间的距离当成是3来计算，这时，数牌的子序列的距离之和与子序列之间的距离之和的总和<=27。
Ⅲ）00100这样的子序列可以当成可以当成字牌的子序列或者数牌中孤张牌的子序列。一般先把其看成是字牌的子序列，除非当这样的子序列个数超过7个时，超过7个的部分必须当成数牌中孤张牌的子序列。
③序列的排序和去重：
Ⅰ）以00分隔的各个子序列的选择去重：
子序列自身进行反转不会影响向听数，所以可以根据子序列和其逆序子序列的比较规则对他们进行选择和去重。
如“一一一二三五六④⑤⑧99东南”：3110110011001002001001，
其中的311011子序列，和其反序列110113序列是重复的，可以根据子序列的比较规则对他们进行选择去重。
比较规则可以直接根据字符串或数值的大小进行比较。
Ⅱ）以00分隔的各个子序列之间的排序：
由于各个子序列的交换顺序不影响向听数，所以可以根据各个子序列之间的比较规则对他们进行选择和去重。
如“一一一二三五六④⑤⑧99东南”：3110110011001002001001，
这个序列和3110110010010010020011序列的向听数是相同的，可以对他们进行选择去重。
可以根据各个子序列的比较关系进行排序，这样就可以达到选择去重的效果。
5、对序列求向听数
可以对手牌进行拆解，使用回溯法、深度优先搜索（DFS）等方法对牌面的拆解进行递归遍历，从而判断手牌的向听数。详情可以参考天凤牌理的计算向听数的代码<syanten1007.js>。
6、编码存储到文件
将序列转换成编码后，将序列的编码及其向听数保存到序列中，可以按如下结构进行存储。
syanten = [{}, {}, {}, ...]
该列表的索引i即为向听数-1（-1向听为和了形，0向听为听牌形），这样就不用再额外保存序列的向听数了，不过这样就需要对所有序列按向听数先进行分类。
syanten[i]为向听数为i-1的所有序列，可以将序列的编码作为字典的key值，这样可以为每个序列额外保存一些信息。如果不需要保存额外信息的话，可以将syanten[i]定义为set等其他哈希结构，方便进行查询。
7、编码的压缩
可以采用差分编码对编码进行压缩，进一步在不降低查询效率的情况下节省存储空间。
编码方式可以采用霍夫曼编码（Huffman Coding）。
