找到最佳数量的拉米风格集的算法？

Question

我正在开发一款纸牌游戏，它使用拉米风格的三张纸牌。从随机选择的卡片中，我需要算法来挑选出哪些卡片能让我得到最多的套数。

我所说的“拉米式三人组”是指:

• 所有三张牌都具有相同的值，就像三张 J 一样。或者
• 所有三张牌都是相同的花色并按顺序排列，就像 7、8、9 都是方 block 。

例如，给定牌:6D、7D、7C、7H、8D、8C、9C、10H
我可以形成集合:{7D, 7C, 7H}，但那将是我唯一能从中得到的集合，而且它不是最优的。
这种情况下的最佳集合是:{ {6D, 7D, 8D}, {7C, 8C, 9C} }

我已经尝试过暴力破解(排列所有给定的卡片，查看排列顺序中的匹配项)，但事实证明这太慢了。这个问题感觉它与其他已解决的问题有相似之处，这就是我在这里问的原因。

Answer 1

如果您有 N 张卡片(N = 8)，您可以在时间 N * (N - 1) * (N - 2) 中枚举集合中所有不同的三元组(N = 8 时得到 336)。这非常快。检查哪些三元组是“拉米式”集合，并将它们作为整数三元组存储在表中(整数表示纸牌的序号)。

这是第一步。现在第二步是进行组合优化并计算最优选择。做到这一点的简单方法是使用回溯搜索。您对找到的一组三元组运行索引 ('i')。首先，您尝试在解决方案中包含“第 i”个三元组，然后从索引 i+1 递归地继续；然后您回溯并确定第“i”个三元组不在解决方案中，然后递归地从 i+1 继续。对此有很多优化，但对于小集合它会工作得很好。

这里是它如何与你的例子一起工作:

卡片:6D、7D、7C、7H、8D、8C、9C、10H

让我们枚举所有可能的三元组:

Cards        Index triple
6D 7D 8D     <0, 1, 4>
7D 7C 7H     <1, 2, 3>
7C 8C 9C     <2, 5, 6>

完整的回溯搜索是这样的:

Decide on <0, 1, 4>:
  <0, 1, 4> INCLUDED:
     <1, 2, 3> CLASHES with <0, 1, 4>
     Decide on <2, 5, 6>:
       <2, 5, 6> INCLUDED:
          Solution with 2 sets (* BEST SOLUTION)
       <2, 5, 6> EXCLUDED:
          Solution with 1 sets
  <0, 1, 4> EXCLUDED:
     Decide on <1, 2, 3>:
        <1, 2, 3> INCLUDED:
           <2, 5, 6> CLASHES with <1, 2, 3>
           Solution with 1 sets
        <1, 2, 3> EXCLUDED:
           Decide on <2, 5, 6>:
             <2, 5, 6> INCLUDED:
                Solution with 1 set
             <2, 5, 6> EXCLUDED:
                Solution with 0 sets

然后您选择集合最多的解决方案(标有星号)。

这实现起来非常简单。试试吧!