algorithm - 减少匹配器的最佳方法

Question

我有一个这样的匹配器:

type matcher struct {
    all  []int
    none []int
    any  [][]int
}

要匹配一个整数数组，它必须包含 all 中的所有整数，不包含 none 中的任何整数，并且必须至少包含一个来自 all 的整数any 中的每个整数数组。我有一个工厂可以轻松构建这样一个匹配器，但是一旦我有了工厂字段，我就需要“扁平化”结构以确保没有任何条款是矛盾的。现在，我拥有的是(伪代码):

all = [0, 1, 2, 3] // means all of these numbers must be present for the matcher to match
any = [[4, 5], [6, 7, 8]] // means one number from each of these groups must be present
none = [9,10] // means none of these may be present
sort(all)
sort(none)
if len(intersections(all, none)) != 0 {
    panic("All and none are contradictory!")
}

for gIndex, group in any {
    sort(group)
    for index, integer in group {
        // If all contains the integer...
        if binarySearch(all, integer) {
            swap(group[len(group)-1], group[index]) // swap the last item with the integer...
            group = group[:len(all)-1] // and truncate the group by one; most efficient way to delete an item.
        }
        // If none contains the integer...
        if binarySearch(none, integer) {
            panic("item in any is also found in none; possible contradiction")
        }
    }
    if len(group) < 1 {
        // delete group from any
    } else if len(group) == 1 {
        // put group[0] (only integer in it) into all, since it must be met
    } else {
        sort(group) // Re-sort the group
        any[gIndex] = group // Update the group
    }
}
removeDuplicates(all)
removeDuplicates(none)
sort2D(any) // Sort by their greatest member
removeDuplicates2D(any) // Go through and remove any duplicate arrays.

all、any 和 none 现在应该简化为最简单的形式，以便检查整数数组是否匹配应该更有效并且没有矛盾。

有没有更好的方法来做到这一点，我在这里遗漏了什么吗？

Answer 1

您的解决方案中至少有两个缺陷。

1. 您要从 any 组中删除 all 中的整数。事实上，如果与 all 有交集，您必须删除整个组而不是删除一个项目。 any 组包含来自 all 的项目只是多余的。

   与 none 组重叠不一定是问题。这些项目实际上可以从 any 组中删除。但是当这导致一个空的 any 组时，您可能想要抛出一个错误。具有空 any 组的匹配器不会匹配任何内容。无论如何，不​​要悄悄地删除空的 any 组!

2. 类似的情况适用于包含其他 any 组的 any 组。考虑以下任何一种选择:

   any = [[4, 5], [4, 5, 6]]
   

   假设 all 和 none 为空。那么你的算法将保持不变。然而，第二组显然是多余的。任何包含第一组中至少一个元素的数组也将匹配第二组。这意味着至少您必须删除所有包含其他超集的any 数组。

我相信这会导致您可以用来比较匹配器的规范形式。然而，我可能错了。