将复杂的过滤规则简化为可比较的形式

Question

我想判断输入的整数数组是否"matches"一组规则

匹配器

Matcher 由一组辅助方法构建而成，用于描述输入数据的规则。这些规则本质上是整数数组的逻辑门：

AND(1, 2) // Requires both 1 AND 2 be present in the input array.
OR(3, 4, 5) // Requires that 3 OR 4 OR 5 be present in the input array.
NOR(6, 7) // Requires that neither 6 NOR 7 be present in the input array.
XOR(8, 9) // Requires that either 8 (X)OR 9 be present in the input array, but not both.

因此，我可以这样说，给定输入数组：

[0, 1, 2, 3]

我可以构建一个 Matcher 像：

AND(OR(0, 1), AND(1, 2) NOR(4))

哪个会匹配输入，因为输入满足：

OR(0, 1) // 0 or 1 is present
AND(1, 2) // Both 1 and 2 are present
NOR(4) // 4 is not present

并且每一项都满足总体 AND 规则。

问题

我需要将匹配器简化为仍然描述规则的最简单和最基本的形式。例如，给定上述匹配器，样本减少可以是：

rules = {
  or: [1, 2],
  xor: [], // No XORs
  nor: [4]
}

每个 rule 有三个子规则数组，由整数或 rules 组成。

注意 OR 是空的，因为 1 无论如何都是必需的，这意味着 OR(0, 1) => [0, 1] 是多余的，因为它必须被满足。

由于 Matchers 需要具有可比性（我需要能够确定基本规则之间的等价性），当我到达时变得有点复杂：

input = [1, 2, 5, 9, 11, 12, 13, 14, 17]

XOR(OR(AND(1, 2), NOR(3, 4), XOR(3 11), AND(11, 14)), AND(1, 5, 17))

现在很多都是多余的and/or自相矛盾，所以我想我能做的就是先把它做成一个树状结构，然后递归它，减少不必要的条目。有更好的方法来做到这一点吗？

我特别在寻找确定性的东西（任何一组输入规则意味着相同的东西产生相同的最终简化形式）。如果有更好的方式来表达这个问题，我很感兴趣，如果规则相互矛盾，reducer 中断并抛出异常也没关系。这是为了在程序中偶尔使用，所以性能不是什么大问题。

Answer 1

你在这里实际处理的是propositional logic。根据它们是否存在于输入数组中，考虑您的命题的整数是假还是真。

您的约束（XOR、AND 等）然后形成一个可满足或不可满足的逻辑公式。实际上很难确定任何给定的公式是否可满足。但是，乍一看这不应该让您担心，因为您只需检查给定的输入是否满足公式。

不幸的是，您实际上要问的是如何确定两个命题公式是否等价。事实证明这同样困难：https://math.stackexchange.com/questions/1050127/how-to-efficiently-determine-if-any-two-propositional-formulas-are-equivalent

将复杂的过滤规则简化为可比较的形式

Reducing complex filter rules to a comparable form

arrays

sorting

algorithm

reduce

匹配器

问题