title: How to search for the largest subset where every pair meets criteria?
body: <p>I hope this isn't more of a statistics question...</p>
  
  <p>Suppose I have an interface:</p>
  
  <pre><code>public interface PairValidatable&lt;T&gt;
  {
      public boolean isValidWith(T);
  }
  </code></pre>
  
  <p>Now if I have a large array of PairValidatables, how do I find the largest subset of that array where every pair passes the isValidWith test?</p>
  
  <p>To clarify, if there are three entries in a subset, then elements 0 and 1 should pass isValidWith, elements 1 and 2 should pass isValidWith, and elements 0 and 2 should pass isValidWith.</p>
  
  <p>Example,</p>
  
  <pre><code>public class Point implements PairValidatable&lt;Point&gt;
  {
      int x;
      int y;
  
      public Point(int xIn, int yIn)
      {
          x = xIn;
          y = yIn;
      }
  
      public boolean isValidWith(Point other)
      {
          //whichever has the greater x must have the lesser (or equal) y
          return x &gt; other.x != y &gt; other.y;
      }
  }
  </code></pre>
  
  <p><a href="https://stackoverflow.com/questions/37898787/finding-largest-subset-where-each-number-in-any-pair-one-number-is-divisible-by">The intuitive idea</a> is to keep a vector of Points, add array element 0, and compare each remaining array element to the vector if it passes the validation with every element in the vector, adding it to the vector if so... but the problem is that element 0 might be very restrictive. For example,</p>
  
  <pre><code>Point[] arr = new Point[5];
  arr[0] = new Point(1000, 1000);
  arr[1] = new Point(10, 10);
  arr[2] = new Point(15, 7);
  arr[3] = new Point(3, 6);
  arr[4] = new Point(18, 6);
  </code></pre>
  
  <p>Iterating through as above would give us a subset containing only element 0, but the subset of elements 1, 2 and 4 is a larger subset where every pair passes the validation. The algorithm should then return the points stored in elements 1, 2 and 4. Though elements 3 and 4 are valid with each other and elements 1 and 4 are valid with each other, elements 2 and 3 are not, nor elements 1 and 3. The subset containing 1, 2 and 4 is a larger subset than 3 and 4.</p>
  
  <p>I would guess some tree or graph algorithm would be best for solving this but I'm not sure how to set it up.</p>
  
  <p>The solution doesn't have to be Java-specific, and preferably could be implemented in any language instead of relying on Java built-ins. I just used Java-like pseudocode above for familiarity reasons.</p>