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

Question

这实际上是一个基于麻将的问题，但是基于罗姆甚至扑克的背景也很容易理解。

在麻将中，14 张牌（牌类似于扑克中的牌）被排列成 4 组和一对。一条街道（“123”）始终只使用 3 个瓷砖，不多也不少。一组相同类型的（“111”）也恰好由 3 个瓷砖组成。这导致总和为 3 * 4 + 2 = 14 个图块。

还有各种例外，例如《坎》或《十三孤儿》，与此处无关。颜色和值范围 (1-9) 对于算法来说也不重要。

我正在尝试确定是否可以按照上述方式安排手牌。由于某些原因，它不仅应该能够处理 14 个图块，还应该能够处理任意数量的图块。 （下一步是找出需要交换多少张牌才能完成一手牌。）

示例：

11122233344455 - 很简单，4 组和一对。
12345555678999 - 123、456、789、555、99
11223378888999 - 123、123、789、888、99
11223344556789 - 不是有效的手牌

我当前尚未实现的想法是这样的：对于每个图块，尝试制作a）一条街道b）一组c）一对。如果没有一个有效（或者有 > 1 对），则返回到上一次迭代并尝试下一个选项，或者，如果这是最高级别，则失败。否则，从剩余图块列表中删除已使用的图块并继续下一次迭代。

我相信这种方法有效，而且速度也相当快（性能是一个“不错的奖励”），但我对你对此的看法很感兴趣。你能想到替代解决方案吗？这个或类似的东西已经存在吗？

（不是作业，我正在学习打麻将。）

Answer 1

街道和集合中的值之和可以除以 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]

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牌之前，所以前2个c4牌将被作为对拾取，留下一个孤儿c4和 2 个 d4，这 3 个图块不会形成有效的集合。

在这种情况下，您需要将 2 个 c4 牌“返回”到手上（并保持手牌排序），并搜索下一个满足条件的牌（值 == 4）。为此，您需要使代码“记住”它已尝试过 c4，因此在下一次迭代中它应该跳过 c4 并查找值 == 4 的其他图块。代码会有点混乱，但可行。

Answer 3

我会把它分成两步。

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

您还可以执行步骤 1.5，仅检查每种类型是否有足够的可用。在这一步和步骤 2 中，您将能够创建通用算法。对于所有数量的图块和可能的组合，第一步都是相同的。