Ensuring only a single formula could ever apply to 4 random elements

Question

I have a list of formulae for combining elements:

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

I want to ensure that given any random 4 elements, there will never be more than 1 applicable formula. For example the formulae below should not be allowed as if I get elements A, B, C and D then both are applicable:

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

Every formula will consist of 3 elements on the LHS and it's the LHS that I want to enforce the rule on.   The elements are sortable, if that helps.

---

An alternative, equivalent problem:

I have a list of an array of 3 elements: List<Element[3]> How do I ensure that no 2 elements appear in more than one array.

---

What would be a reasonably efficient (runtime speed) way of doing this for a large number of elements and a large number for formulae (beyond brute forcing)?

Answer 1

Essentially this comes down to a exclusion problem: From your example data,

• the first formula works on the set (A,B,C,X) or maybe (A,B,C) if X is a constant
• the second formula works on (D,E,F,Y) or (D,E,F)
• etc

and you want to make sure, that any new entry to the list

• Doesn't operate on a set already in the list (like (A,B,C[,X]))
• Doesn't operate on a subset of an entry already in the list (like (A,B)), as in this case the input tuple (A,B,C[,X]) would work on an already existing formula AND the new one

Depending on the size of the tuples, creating an exhaustive list of subsets can be expensive or not

This should work on small sets (cheap listing of subsets)

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