2023年2月13日记录
2023年2月13日记录
Rummikub 游戏：https://en.wikipedia.org/wiki/Rummikub Rummikub 游戏网站：http://www.rummy-games.com/rules/rummikub.html
【论坛】Rummikub algorithm ：https://cs.stackexchange.com/questions/85954/rummikub-algorithm 【ppt】The Complexity of Rummikub Problems: https://ml.informatik.uni-freiburg.de/wp-content/uploads/papers/15-BNAIC-Complexity-slides.pdf 【论文】The Complexity of Rummikub Problems https://arxiv.org/pdf/1604.07553.pdf 【论文】The Complexity of Rummikub Problems https://liacs.leidenuniv.nl/~takesfw/pdf/rummikub.pdf 【源码】 https://github.com/machocam/rummikub 【论文】Solving Rummikub Problems by Integer Linear Programming
以色列麻将
Tileset parameters
Numbers n (default: 13)
Suits/colors k (default: 4)
Duplicates m (default: 2)
3: 4+4 = 8
2: 4+4+3 = 11
1: 4+4+4+2 = 14
0: 4×4 + 1 = 17
3^17
=3 × 3^16
Dp[n][pos][hash0][hash1][hash2][hash3]
N=13, 待处理的最大的数字
Pos=4, 处理颜色的最大
Hash: 映射的有效值
优化项1：除了h=0，其他的不可能为 2.
1）单独看最大数字的可能情况
群组：
h=0 代表处理到第一个数字， 值范围3个， [{0},{1},{2}]
h=1 代表处理到第二个数字， 值范围4个， [{0,0},{0,1},{1,0},{1,1}]
h=2 代表处理到第三个数字， 值范围8个， [{0,0,0}, {0,0,1}, {0,1,0}, {0,1,1}, {1,0,0}, {1,0,1}, {1,1,0}, {1,1,1}]
h=3 代表处理到第四个数字， 值范围16个，[{0,0,0,0},{0,0,0,1},{0,0,1,0},{0,0,1,1},{0,1,0,0},{0,1,0,1},{0,1,1,0},{0,1,1,1},{1,0,0,0},{1,0,0,1},{1,0,1,0},{1,0,1,1},{1,1,0,0},{1,1,0,1},{1,1,1,0},{1,1,1,1}]
顺子： 31 个
h=0，代表处理到第一个数字，值范围 1 个 []
h=1，代表处理到第二个数字，值范围 2 个 [2^1]
h=2，代表处理到第三个数字，值范围 4 个 [2^2]
h=3，代表处理到第四个数字，值范围 8 个 [2^3]
h=4，代表处理到第五个数字，值范围 16 个 [ 2^4]
f0(n, 31, 31)
f1(n, 15, 31, 31)
f2(n, 7, 31, 31, 31)
f3(n, 3, 31, 31, 31, 31))
空间：O(n * (2^5)^k)
F(n, l, r) 含义 [n, n+l) 都减2， [n+l, n+r) 都减一。
f(n, l1, r1, l2, r2, l3, r3, l4, r4) = {
"flag" : 0,
"pre" : [n, l1, r1, l2, r2, l3, r3, l4, r4]
}
