找到最佳数量的拉米式集合的算法？

Question

我正在开发一种使用拉姆风格的三张牌的纸牌游戏.从随机选择的卡片中,我需要算法来挑选哪些卡片能够获得最高数量的卡片.

通过"拉米式三件套"我的意思是:

• 所有三张牌都有相同的价值,比如三个杰克.要么
• 所有三张牌都是相同的套装和顺序顺序,如7,8,9所有的钻石.

例如,给定卡片: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'th三元组,然后递归地从索引i + 1继续; 然后你回溯并决定'i'th triple 不在解决方案中,并从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

然后,您选择具有大多数集合的解决方案(标有星号).

这很容易实现.试试吧!