c# - 确保只有一个公式可以应用于 4 个随机元素

Question

我有一个组合元素的公式列表:

A + B + C = X
D + E + F = Y
G + H + I = Z

我想确保给定任何随机的 4 个元素，永远不会有超过 1 个适用的公式。例如，下面的公式不应该被允许，因为如果我得到元素 A、B、C 和 D 那么两者都适用:

A + B + C = X
B + C + D = Y

每个公式都将由 LHS 上的 3 个元素组成，我想在 LHS 上执行规则。如果有帮助，元素是可排序的。

---

另一个等价的问题:

我有一个包含 3 个元素的数组列表:List<Element[3]>如何确保没有 2 个元素出现在多个数组中。

---

对于大量元素和大量公式(超越暴力破解)，什么是合理有效(运行时速度)的方式？

Answer 1

本质上这归结为排除问题:根据您的示例数据，

• 第一个公式适用于集合 (A,B,C,X) 或者如果 X 是 (A,B,C)一个常数
• 第二个公式适用于 (D,E,F,Y) 或 (D,E,F)
• 等等

并且您想确保列表中的任何新条目

• 不对列表中已有的集合进行操作(如 (A,B,C[,X]))
• 不对列表中已有条目的子集进行操作(如 (A,B))，因为在这种情况下，输入元组 (A,B,C[,X]) 将对已经存在的条目进行操作公式和新公式

根据元组的大小，创建一个详尽的子集列表可能会很昂贵，也可能不会很昂贵

这应该适用于小集合(廉价的子集列表)

Keep dictionary of formulas
On new formula
  Normalize variable list (e.g. (D,A,c)=>"ACD")
  Check if normalized variable list exists in dictionary
  If it exists, reject new formula and break
  For all subsets of variable list
    Check if normalized variable list of subset exists in dictionary
    If it exists, reject new formula and break
  End For
End On