나는이 통계 질문하지 더 희망 ...모든 쌍이 기준을 충족시키는 가장 큰 하위 집합을 찾는 방법은 무엇입니까?
내가 인터페이스 있다고 가정하자 : 나는 가장 큰 부분 집합을 찾을 어떻게, 내가 PairValidatables의 큰 배열이있는 경우 지금
public interface PairValidatable<T>
{
public boolean isValidWith(T);
}
을 모든 쌍이 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 요소를 추가하고,이 벡터의 모든 요소가 검증을 통과하면 벡터와 나머지 각 배열 요소를 비교하는 것이다 if vector ... 그렇지만 문제는 요소 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 내장 기능에 의존하지 않고 모든 언어로 구현할 수있는 것이 바람직합니다. 방금 익숙한 이유로 자바와 비슷한 의사 코드를 사용했습니다.
배열의 각 항목에 대해 동일한 알고리즘을 실행하고 다른 항목과 비교하여 isValidWidth를 가장 성공적으로 반환 한 결과를 반환하겠다고 말하고 싶습니까? – Stephan
@ 스탄 매우. 부분 집합의 모든 쌍은 isValidWith에서 true를 반환해야합니다. 예를 들어, a는 b와 유효하고 b는 c와 유효 할 수 있지만 c는 a와는 유효하지 않을 수 있습니다. 이는 a 또는 c가 생략되어야 함을 의미합니다. 내 예제 메서드가 그런 식으로 동작하지만 솔루션에 포함될 메서드가 포함되어 있는지 확실하지 않습니다. – Devsman
예제에서 3 개 이상의 항목을 포함하도록 질문을 확장 할 수 있으며 결과물은 무엇입니까? – Stephan