将卡片与一组规则匹配的算法

Question

我遇到了一个奇怪的问题，我似乎无法解决这个问题。我马上开始。

问题是将一组卡片与一组规则匹配。

可以将一组规则定义为字符串。它由 <suit>:<value> 的逗号分隔元组组成。 .例如H:4, S:1应该匹配红心四和黑桃 A。也可以使用通配符，例如 *:*匹配任何卡片，D:*匹配钻石套装中的任何卡片，并且 *:2匹配任何花色的二。规则可以用逗号组合:*:*,*:*,H:4如果它包含 2 张随机卡片和红心四，则会匹配一组卡片。

到目前为止一切顺利。为此编写的解析器很容易直接编写。棘手的部分来了。

为了便于编写这些规则，可以使用另外两种结构来表示花色和值。这些是 < (花色和值(value)合法)和+n (仅对值合法)其中 n 是一个数字。 <表示“与上一场比赛相同”和+n表示“比上一场比赛高 n”。一个例子:

*:*, <:*, *:<

意思是:匹配任意一张牌，然后匹配一张与第一场相同花色的牌，接下来再匹配另一张与第二场相同点数的牌。这手牌会匹配:

H:4,H:8,C:8

因为红心四和红心八是同一花色，而红心八和梅花八是相同的值。

只要所有规则都匹配，就允许有更多的牌(因此，将 C:10 添加到上述手牌仍然符合规则)。

我解决这个问题的第一个方法基本上是采用应该匹配的一组卡片，尝试将第一条规则应用于它。如果匹配，我继续下一个规则并尝试从卡片组中匹配它，依此类推，直到所有规则都匹配，或者我找到一个不匹配的规则。这种方法(至少)有一个缺陷，考虑上面的例子:*:*,<:*,*:< , 但卡片的顺序是:H:8,C:8,H:4 .

• 它将匹配第一条规则的 H:8。 Matched: H:8
• 接下来，它会尝试找到一个花色相同的花色(红心)。有红心四。 Matched: H:8, H:4
• 继续，它想找到一张具有相同值(四)的卡片，但失败了。

我不希望卡片组的排序方式对结果产生任何影响，就像在上面的示例中那样。如果我能想到任何适用于任何规则集的好策略，我就可以对这些卡片进行排序。

我不知道卡片的数量或规则的数量，因此蛮力方法是不可行的。

感谢您阅读到这里，感谢您提供的任何提示或见解。

Answer 1

您的问题实际上是一个排序问题。这是一个简单的版本:

给定一个输入数字序列和一个模式，将它们重新排序以符合模式。该模式可以包含“*”，表示“任意数字”和“>”，表示“大于前一个数字”。

例如，给定模式 [* * >>] 和序列 [10 10 2 1] 这样的排序存在并且它是 [10 1 2 10]。一些输入可能没有输出，其他的可能有 1 个，甚至有很多(想想输入 [10 10 2 1] 和模式 [* * * *])。

我想说的是，一旦您有了这个简化问题的解决方案，切换到您的问题只是添加另一个维度和一些运算符的问题。很抱歉没有提供更多帮助:/。

乐。请记住，如果允许的字符符号是有限的(即 4)以及允许的数字(即 9)，事情可能会变得更容易。