Я надеюсь, что это не больше вопрос статистики ...Как найти самое большое подмножество, где каждая пара соответствует критериям?
Предположим, у меня есть интерфейс:
public interface PairValidatable<T>
{
public boolean isValidWith(T);
}
Теперь, если у меня есть большой массив PairValidatables, как я могу найти наибольшее подмножество из этого массива, где каждая пара проходит тест isValidWith?
Чтобы уточнить, есть ли три элемента в подмножестве, тогда элементы 0 и 1 должны пройти isValidWith, элементы 1 и 2 должны пройти isValidWith, а элементы 0 и 2 должны пройти isValidWith.
Пример,
public class Point implements PairValidatable<Point>
{
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 > other.x != y > other.y;
}
}
The intuitive idea является сохранение вектора точек, добавить элемент массива 0, и сравнить все оставшиеся элементы массива к вектору, если он проходит проверку с каждым элементом в векторе, добавив его к вектору, если это так ... но проблема в том, что элемент 0 может быть очень ограничительным. Например,
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);
Перебор, как указано выше даст нам подмножество, содержащее только элемент 0, но подмножество элементов 1, 2 и 4, является большим подмножеством, где каждая пара проходит проверку. Затем алгоритм должен вернуть точки, хранящиеся в элементах 1, 2 и 4. Хотя элементы 3 и 4 действительны друг с другом, а элементы 1 и 4 действительны друг с другом, элементы 2 и 3 не являются, ни элементами 1 и 3. Подмножество, содержащее 1, 2 и 4, является более крупным подмножеством, чем 3 и 4.
Я бы предположил, что для решения этого вопроса лучше всего использовать алгоритм дерева или графа, но я не уверен, как его настроить.
Решение не обязательно должно быть специфичным для Java и предпочтительно может быть реализовано на любом языке, вместо того чтобы полагаться на встроенные Java-модули. Я просто использовал псевдокод, подобный Java, для ознакомления.
Вы пытаетесь сказать, что хотите использовать один и тот же алгоритм для каждой записи в массиве и возвращать какой бы то ни было результат наиболее успешных результатов isValidWidth при проверке всех остальных записей? – Stephan
@Stephan Не совсем. Каждая пара в подмножестве должна возвращать значение true из isValidWith. Например, a может быть действительным с b и b может быть действительным с c, но c может быть недействительным с a. Это означает, что либо a, либо c должны быть опущены. Я не уверен, что мой примерный метод будет вести себя таким образом, но решение должно включать методы, которые будут. – Devsman
можете ли вы расширить свой вопрос, включив в пример более 3 записей, и что вы ожидаете от вывода? – Stephan