寻找手中街道和同类的算法

13
这实际上是一个基于麻将的问题,但以罗密欧或扑克牌为背景也很容易理解。在麻将中,14张牌(类似于扑克牌)被排列成4组和1对。一个顺子(“123”)总是使用恰好3张牌,不多不少。同样的牌型(“111”)也由恰好3张牌组成。这导致了3 * 4 + 2 = 14张牌的总数。有各种例外情况,如杠或十三幺,这里不相关。颜色和值范围(1-9)对算法也不重要。我正在尝试确定手牌是否可以按上述方式排列。出于某些原因,它不仅应该能够处理14张牌,而且应该能够处理任意数量的牌。(下一步是找出需要交换多少张牌才能完成手牌。)例如:11122233344455 - 很容易,4组和1对;12345555678999 - 123、456、789、555、99;11223378888999 - 123、123、789、888、99;11223344556789 - 不是有效的手牌。
我的当前尚未实现的想法是:对于每个牌,尝试制作a)街道b)集c)对。如果没有可行的方案(或有超过1个对),则返回上一次迭代并尝试下一个选项,或者如果这是最高级别,则失败。否则,从剩余牌的列表中删除已使用的牌,并继续下一次迭代。我相信这种方法可行且速度合理(性能是“额外好处”),但我对您对此的看法很感兴趣。您能想到其他解决方案吗?是否已经存在类似的解决方案?(不是作业,我正在学习打麻将

1
哦,我知道了,我会使用正则表达式!!11! - mafu
4
有些人面对问题时会想:“我知道,我用正则表达式来解决。”现在他们有了两个问题。~ Jamie Zawinski :) - Draco Ater
你可以尝试分解最多三个集合来形成一条街道(或者反过来)。这样可以吗? - Dr. belisarius
说真的,我认为正则表达式在这里可能很有用。我手头没有语法,因为我很少使用它,但应该很容易。至少对于一个“临时”解决方案来说,不强调速度和可扩展性。 - mafu
@bel:是的,只要最终得到4组街和一对牌,你可以打散任何东西。哦,对了,在街道中没有1/9环绕。 - mafu
3个回答

18

在一条街和一个集合中所有数值的总和可以被3整除:

  • n + n + n = 3n
  • (n-1) + n + (n + 1) = 3n

因此,如果您将解决方案中所有数字相加,您将得到一个形如3N + 2M的数字,其中M是对中的瓦片的值。对于每个M的值,除以三后的余数(total % 3)是:

total % 3 = 0  -> M = {3,6,9}
total % 3 = 1  -> M = {2,5,8}
total % 3 = 2  -> M = {1,4,7}

因此,您只需要尝试三个可能的对而不是九个,这基于简单的加法。对于每个可能的对,删除具有该值的两个瓷砖,并进入算法的下一步以确定是否可行。

一旦您得到这个结果,就从最低值开始。如果该值的瓷砖少于三个,则它们必然是一个序列的第一个元素,因此删除该序列(如果无法删除,因为缺少瓷砖n+1或n+2,则表示手牌无效)并继续进行下一个最低值。

如果最低值至少有三个瓷砖,则将它们作为一组删除(如果您问“如果它们是序列的一部分怎么办?”请考虑如果是这样,那么还有三个n+1和三个n+2的瓷砖,也可以成为一组),然后继续进行。

如果到达空手牌,则手牌有效。

例如,对于您的无效手牌,总数为60,这意味着M = {3,6,9}:

Remove the 3: 112244556789
 - Start with 1: there are less than three, so remove a street
   -> impossible: 123 needs a 3

Remove the 6: impossible, there is only one

Remove the 9: impossible, there is only one

使用您提供的第二个示例12345555678999,总和为78,这意味着M = {3,6,9}:

Remove the 3: impossible, there is only one

Remove the 6: impossible, there is only one

Remove the 9: 123455556789
 - Start with 1: there is only one, so remove a street
   -> 455556789
 - Start with 4: there is only one, so remove a street
   -> 555789
 - Start with 5: there are three, so remove a set
   -> 789
 - Start with 7: there is only one, so remove a street
   -> empty : hand is valid, removals were [99] [123] [456] [555] [789]

你的第三个例子11223378888999总共有78个,这会导致回溯:

Remove the 3: 11227888899
 - Start with 1: there are less than three, so remove a street
   -> impossible: 123 needs a 3

Remove the 6: impossible, there are none

Remove the 9: 112233788889
 - Start with 1: there are less than three, so remove streets
   -> 788889
 - Start with 7: there is only one, so remove a street
   -> 888
 - Start with 8: there are three, so remove a set
   -> empty, hand is valid, removals were : [99] [123] [123] [789] [888]

非常好的答案。我仍在思考是否存在任何导致错误拒绝的情况...但我还没有找到一个例子。 - mafu
没有问题。算法的正确性证明已经提供了;-) - Victor Nicollet
很棒的解释和例子。这对我帮助很大! - Nick Kitto
请注意,如果我们知道一手牌只由序列组成,那么它总是可以通过从最小数字开始强制生成序列来确定。例如 122333445567 -> 123 234 345 567。因此,更实际的做法是:1)按照上述方法找到一对;2)通过试错检查三元组。对于一个14张麻将手牌,最多有4个可能的三元组,因此需要进行16次尝试。3)检查剩下的手牌是否可以分成所有的序列。对于每个14张麻将手牌,最多需要40次尝试,比回溯算法容易得多。 - user2341726

3

有一个特殊情况需要进行一些调整才能正确处理。当存在三张连续的牌和一对相同点数但不同花色时就会出现这种情况。

让 b 代表筒子,c 代表条子,d 代表万字,试试这手牌:

b2,b3,b4,b5,b6,b7,c4,c4,c4,d4,d4,d6,d7,d8

d4,d4 should serve as the pair, and c4,c4,c4 should serve as the run-of-3 set.

但是由于3个"c4"瓷砖出现在2个"d4"瓷砖之前,前两个"c4"瓷砖将被作为一对拿起, leaving an orphan c4 and 2 d4s,并且这三个瓷砖不会组成有效的集合。
在这种情况下,您需要将2个c4瓷砖“返回”到手中(并保持手中排序),并搜索满足条件(value == 4)的下一个瓷砖。要做到这一点,您需要使代码“记住”它已尝试过c4,因此在下一次迭代中,它应跳过c4并寻找其他值== 4的瓷砖。代码会有点凌乱,但是可行的。

仔细查看后发现我们不需要“记住”失败的瓷砖。在尝试了一对候选者并未能清理手牌后,我们可以继续循环并向下搜索列表。半伪代码: - Larry Chu
int[][] pair_idx = {{3,6,9},{2,5,8},{1,4,7}};
for (int j = 0; j < 3; j++) {
col = pair_idx[row][j];
for (k = 0; k < tmp.cnt; k++) {
if (k < hand.length - 1 && hand[k].num == col && hand[k+1].num == col) {
移除这两张牌
寻找手牌中的所有牌组
如果手牌为空
返回真
否则 {
恢复手牌
继续循环
}
}
}
}
- Larry Chu
尝试在行末使用“2个空格”,但无法使换行符正常工作? - Larry Chu

1
我会将它分成两个步骤。
1. 找出可能的组合。使用这些数字进行全面检查是可行的。此步骤的结果是一个组合列表,每个组合都有一个类型(集、街或对)和带有所使用卡片的模式(可以是位图)。
2. 根据先前的信息确定可能的组合集合。这就是位图派上用场的地方。使用位运算符,您可以查看不同组合器的相同图块的使用重叠。
您还可以执行第1.5步,只需检查是否有足够的每种类型即可。在这一步和第二步,您将能够创建通用算法。第一步对于所有数量的瓷砖和可能的组合都是相同的,并且可以快速完成。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接