Geo*_*ett 6 c# algorithm permutation
我有一个组合元素的公式列表:
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个元素出现在多个数组中.
对于大量元素和大量公式(除了暴力强制)这样做的合理有效(运行时速度)方法是什么？
您可以将方程组的约束表示为图形。顶点是元素，n[i]元素在方程 中i。对于方程i，因此存在n[i]*(n[i]-1)/2元素对；这些成为边缘。迭代方程，将边添加到图中。每当您想要添加已经存在的边缘时，您就会发现冲突。
对于每条边，您可以存储一组将生成边的方程编号；这样可以识别具体的冲突，而不仅仅是冲突的存在。
让N为方程的数量和M方程中元素最多的元素的数量。时间复杂度是O(M^2*N)，空间复杂度也是 。如果所有方程都有固定数量的元素，则时间和空间的使用将为O(N)。