Algorithm for finding the optimal group of compatible elements

Question

I have a set of entities, and I need to group these objects into groups called specie . A set of all types defined by Universe calls, and an object must belong to one and only one instance. For this, I have a logical non-transition function called f , which returns if the two objects passed by the parameters are compatible. A specie defined by a group of objects compatible with each other, and a Universe is defined by a group of species that are not completely compatible with each other, assuming that the compatibility of two types is determined by the compatibility of all of its entities.

How can I define a universe that contains the least number of views available for a given set of objects?

I tried as follows, and my function returns a valid universe, but not the one that has the least number of views.

 public class Specie { private List<Entity> individuals; public Specie() { this.individuals = new ArrayList<>(); } public boolean matches(Entity e) { for (Entity s : this.individuals) { if (!f(s, e)) { return false; } } return true; } public void add(Entity i) { this.individuals.add(i); } } private static int numberOfSpeciesRecursive(List<Entity> entities, List<Specie> universe) { if (entities.size() == 0) { return 0; } else { List<Entity> remains = new ArrayList<>(); Specie specie = new Specie(); for (Entity e : entities) { if (specie.matches(e)) { specie.add(e); } else { remains.add(e); } } universe.add(specie); return 1 + numberOfSpeciesRecursive(remains, universe); } } 

Answer 1

Consider the entities as vertices of the graph and add edges between the vertices if the entities are compatible.

In this resulting column, your view definition matches the definition of clique .

Therefore, the problem of finding the minimum number of views is equivalent to covering the graph with the least number of clicks. This issue is known as minimal click cover and NP-full.