algorithm - 基于条件的快速匹配元组

Question

我正在寻找解决以下问题的快速算法。

规则由有关元组的子句的联合表示。子句指定两个元组项之间的关系。例如T(1)[2] = T(3)[1]表示:the second item in the first tuple must be equal to the first one in the third .

所以规则可以是:T(1)[2] = T(3)[1] AND T(1)[1] > T(2)[1]

通用规则:

• 子句:(T(j)[i] op T(k)[l])
• 条件:Clause (AND Clause)*
• 支持的运营商:= , != , > , < , <= , >=

算法接收这样的规则和元组列表，其中每个项目都是一个数字:

(i11 i12 ... i1n)
...
(ik1 ik2 ... ikm)

元组长度不同，数量未知。列表中的元组可以按任何顺序排列。

算法将从输入中输出符合规则的所有元组组合。

例子:

规则:T(1)[1] = T(2)[1] AND T(1)[3]>T(3)[1]

元组:

`(1 2 3 4)`   T1
`(3 2 4)'     T2
`(4)`         T3
`(1 5 3 6 7)` T4

将输出以下组合:

• T(1): T1, T(2): T4, T(3): T2
• T(1): T4, T(2): T1, T(3): T2

基本上它将识别哪些元组可以替换每个 T(i)，以便它规则为真。

是否有众所周知的算法可以快速完成此操作？有什么建议吗？

谢谢，

一个

Answer 1

因为你需要列出所有可能的分配，而不是计算它们的数量，例如，这可能更容易(虽然我不这么认为)，唯一的方法可能是实现 backtracking解决方案。

编辑: 具体来说，因为原始列表有 N! 个排列(其中 N 是元组的数量)可能满足约束(在最坏的情况下)，并且您需要列出这些约束，O(N!) 的上限很紧。