Ensuring that only one formula can ever be applied to 4 random elements

Question

I have a list of formulas for combining elements:

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

I want to make sure that for any random 4 elements there will never be more than 1 applicable formula. For example, the formulas below should not be allowed as if I were getting the elements A, B, C and D, then both are applicable:

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

Each formula will consist of 3 elements on the LHS, and LHS - to include the rule. Items are sorted if this helps.

---

Alternative, equivalent problem:

I have a list from an array of three elements: List<Element[3]> How can I guarantee that there are no two elements in several arrays.

---

What would be efficient enough (execution speed) for this for a large number of elements and a large number for formulas (except for rough forcing)?

Answer 1

You can represent the constraints on a set of equations in a graph. Vertices are elements, elements n[i] in equation i . For equation i there exist, therefore, pairs of elements t23. they become edges. We go over the equations by adding edges to the graph. At any time, when you want to add an edge that is already present, you have discovered a conflict.

For each edge, you can save a set of numbers of equations that will generate an edge; this allows you to identify specific conflicts, not just conflicts.

Let N be the number of equations and M number of elements in the equation with most elements. The time complexity is O(M^2*N) , as well as the spatial complexity. If all equations have a fixed number of elements, then the use of time and space will thus be O(N) .

Answer 2

In essence, this boils down to an exception problem: from your example data

• the first formula works on the set (A, B, C, X) or, possibly, (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 in the list

• Does not work with an already installed set (for example, (A, B, C [, X])
• It does not work on a subset of the record already in the list (for example, (A, B)), since in this case the input tuple (A, B, C [, X]) will work on the already existing formula AND new

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 list of subsets)

 Keep dictionary of formulas On new formula Normalize variable list (eg (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 

Answer 3

This decision is inspired by the decision of Michael J. Barber.

• Initialize hash table

• When you have an equation with variables M, add all combinations with size M-1 to the hash table. For example: for A + B + C + D = Z add (A, B, C), (A, B, D), (A, C, D) and (B, C, D)

  / li>

• If you want to test the feasibility of a new equation with variables M, check if all subsets of M-1 are in the hash.

Difficulty: O (mnlog (mn)).

Answer 4

You can define this problem on the other hand: there is no pair of formulas in which the union of elements contains less than 5 elements. Which indicates an algorithm that compares each pair of formulas if they pass this test. I know that his brute force, but I can not imagine anything better.

Answer 5

Perhaps you can use some of the LINQ dialing operations. Since you described your problem as a list of lists, wanting to “ensure that there are no two items in multiple lists,” cannot also be described as checking if there is an intersection between any lists? Or am I a little here?

James Michael Hare is a good article on the various dialing operations available in LINQ. You can start by viewing :-)

Answer 6

Save your values ​​in a matrix and make sure that the matrix [i] [j]! = Matrix [k] [j] with i! = K.

Update:

This approach is often used in solving linear equation problems. Elements in the matrix are coefficients of polynomial functions. Then you can work between the lines to take the matrix into special forms.

But in this case, you only need to save your elements in the matrix and check the matrix before adding a row (some combination of elements).

This approach has the advantage that it is most effective, but you need to properly handle the initial size and resizing strategy.

Update 2:

 A + B + C = X B + C + D = Y m[0][1] = B m[1][0] = B 

These examples break the rule matrix [i] [j]! = Matrix [k] [j] with i! = K

Then you cannot use the formulas B + C + D = Y due to A + B + C = X.