算法可以找到街道和同类手

Question

这实际上是一个基于Mahjong的问题，但是基于扑克的背景也很容易理解。

在Mahjong中，14瓷砖（瓷砖就像扑克中的卡片）被安排为4套和一对。一条街道（“ 123”）总是使用3块瓷砖，而不是更少而不是更少。一组相同的（“ 111”）也包含3个瓷砖。这导致3 * 4 + 2 = 14图块的总和。

这里有各种例外，例如Kan或13个孤儿，在这里无关紧要。颜色和价值范围（1-9）对于算法也不重要。

我试图确定是否可以按照上述方式安排手。由于某些原因，它不仅应该能够处理14个瓷砖。 （下一步是找到需要交换多少瓷砖才能完成一只手。）

例子：

11122233344455 - 足够容易，4套和一对。
12345555678999 - 123, 456, 789, 555, 99
11223378888999 - 123, 123, 789, 888, 99
11223344556789 - 没有有效的手

我目前且尚未实现的想法是：对于每个瓷砖，请尝试使a）街道b）A集c）一对。如果无效（或将有> 1对），请返回上一个迭代，然后尝试下一个选项，或者，如果这是最高级别，则失败。否则，从剩余瓷砖列表中删除所用的瓷砖，然后继续进行下一个迭代。

我相信这种方法有效，并且也将非常快（性能是“不错的奖励”），但是我对您对此的看法感兴趣。您能想到替代解决方案吗？这或类似的东西已经存在吗？

（不是作业， 我正在学习玩Mahjong。)

Answer 1

街道和集合中的价值的总和可以除以3：

• n + n + n = 3n
• （n-1） + n +（n + 1）= 3n

因此，如果将所有数字添加在一起，将所有数字添加在一起，则将获得许多3n + 2m的表单，其中M是该对中瓷砖的值。该部门的其余部分由三个（total % 3），对于m的每个值：

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

因此，您只需基于简单的添加而尝试三个可能的对，而不必测试九对。对于每个可能的对，请删除具有该值的两个图块，然后继续进入算法的下一步以确定是否可能。

一旦有了这个，请从最低值开始。如果该值少于三个瓷砖，则意味着它们一定是街道的第一个元素，因此请拆除该街道（如果您不能因为缺少Tiles N+1或N+2，则意味着手无效），然后转到下一个最低值。

如果至少有三块价值最低的砖tile 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]

您的第三个示例11222337888999总共有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]

Answer 2

有一种特殊情况，您需要进行一些重新工作以使其正确。当有一个具有相同价值的对（但穿着不同的西装）时，就会发生这种情况。

让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 TILESS之前，因此将把前2个C4瓷砖当作对，留下孤儿C4和2 D4，而这3个瓷砖不会形成有效的集合。

在这种情况下，您需要将2个C4瓷砖返回手（并保持手工分类），并搜索满足条件的下一个瓷砖（值== 4）。为此，您需要使代码“记住”它尝试过C4，因此在下一个迭代中，它应该跳过C4，并寻找具有值== 4的其他瓷砖。代码会有点混乱，但可行。

Answer 3

我会将其分解为2步。

1. 找出可能的组合。我认为对于这些数字，详尽的检查是可行的。此步骤的结果是组合列表，每个组合都有类型（集合，街道或对），并且具有所使用的卡的图案（可能是位图）。
2. 有了先前的信息，请确定可能的组合收集。这是位图会派上用场的地方。使用位运算符，您可以看到不同组合器的同一瓷砖使用中的重叠。

您也可以执行步骤1.5，只需检查一下是否有足够的每种类型。此步骤和步骤2将是您可以创建一般算法的地方。对于所有瓷砖数量和可能的组合，第一步将相同。