Найти все группы, отвечающие одному критерию

Question

У меня есть n элементов, каждый из которых имеет два атрибута int без знака x и y.

Теперь я хотел бы узнать, все группы, которые соответствуют следующим условиям:

A.x >= B.y и B.x >= A.y.

Группы могут быть в числе 2, 3, ..., n. Например, A, B, C могут удовлетворить это требование друг с другом, поэтому это образует группу 3.

Элементы из двух или более групп могут перекрываться.

Как найти их эффективно?

Это реальная проблема, возникающая в моей работе, а не проблема с кодированием/алгоритмом.

Answer 1

Вы ищете cliques на графике. Узлы - это элементы, с ребрами, расположенными между двумя узлами, если они удовлетворяют вашему условию совместимости.

Сложно создавать клики, и есть библиотеки, которые помогут вам в этом. Проблема нахождения максимальной клики в общем графике NP-жесткая, однако, как правило, нет эффективного алгоритма для этого.

С другой стороны, в вашем случае, похоже, больше структуры, которая может помочь. Если я правильно понимаю, в клике в вашей ситуации все переменные x должны быть больше всех y-переменных (с один возможное исключение, см. Ниже), поэтому вы можете генерировать клики, просто выбирая некоторое число c и включая все элементы, которые удовлетворяют как x> = c, так и y < = c.

Я считаю, что вы можете искать максимальные и даже максимальные клики в этом случае, позволяя параметру c варьироваться от минимума x и y до максимума, а для каждого c подсчитывать количество элементов, удовлетворяющих условию x > = c, y < = c. Функция count будет ступенчатой ​​функцией, которая увеличивается или уменьшается на единицу, когда c = некоторые x или y.

Легко доказать, что этот метод генерирует клики. С немного больше работы мы можем увидеть, как быстро генерировать все клики. Во-первых, позвольте мне определить концепцию retrograde для элемента. Элемент A является ретроградным, если A.y> A.x. Предложение: клика может иметь не более одного ретроградного элемента. Доказательство. Если B также находится в клике, то B.x> = A.y> A.x> = B.y, поэтому B не является ретроградным. Кроме того, если клика содержит ретроградный элемент, то каждый другой элемент клики удовлетворяет условию B.x> = c и c> = B.y, для некоторого c (а именно c = A.x, или c = A.y, или некоторого c между ними).

С другой стороны, если клика не содержит ретроградного элемента, то каждый элемент клики удовлетворяет условию A.x> = A.y и A.x> = B.y, поэтому все y ограничены сверху на min x; аналогично все x ограничены снизу max y. Поэтому в этом случае вы можете выбрать c = min x или max y.

Другими словами, каждая клика является подмножеством одной из следующих клик: клика заключалась в том, что каждый элемент A удовлетворяет A.x> = c и c> = A.y для некоторого фиксированного c; или кликой с одним ретроградным элементом R, в котором все остальные элементы удовлетворяют условию A.x> = R.y и R.x> = A.y.Это должно дать все максимальные клики в чем-то между O (n) и O (n^2) временем; вы можете выбрать максимальную клику из набора максимальных клик.

Answer 2

Сортируйте данные по x и y +, затем установите пересечения.

Это затрудняет задачу. Не пытайтесь набросить на нее теоретическую модель фантазий (клика, кластеризация и т. Д.), Но нарисуйте визуально то, что вы ищете.