나는 이미 stackoverflow 에서이 질문을 했지만이 사이트에 더 적합 할 수 있습니다.
문제는:
서명되지 않은 정수의 N 쌍이 있습니다. 정렬해야합니다. 쌍의 끝 벡터는 각 쌍의 첫 번째 숫자에 따라 감소하지 않고 각 쌍의 두 번째 숫자에 의해 증가하지 않아야합니다. 각 쌍은 어느 시점에서든 첫 번째 요소와 두 번째 요소를 교환 할 수 있습니다. 때로는 해결책이 없으므로 예외를 던져야합니다.
예:
in pairs:
1 5
7 1
3 8
5 6
out pairs:
1 7 <-- swapped
1 5
6 5 <-- swapped
8 3 <-- swapped
^^ 쌍을 바꾸지 않으면 솔루션을 구축 할 수 없습니다. 따라서 쌍 (7, 1), (3, 8) 및 (5, 6)을 바꾸고 결과를 만듭니다. 또는
in pairs:
1 5
6 9
out:
not possible
감사
편집하다:
SO의 Tom Sirgedas가 최상의 솔루션을 제안했습니다 . 구현하기 쉽고 O (log (n) * n)에서 작동합니다. 답변과 관심에 감사드립니다. 나는 mjqxxxx 분석을 정말로 즐겼다.
답변
두 쌍의 및 p 2 = ( a 2 , b 2 ) 는 정렬 된 목록에서 순서를 바꾸지 않고 순서대로 배치 할 수 있으면 스왑이 호환되지 않는다고 가정 하십시오. 이 사실 인 경우 중 어느 하나 ( 1 ≤ 2 ∧ B 1 ≥ B 2 ) 또는 ( 2 ≤ 1 ∧ B 2 ≥ B
p1=(a1,b1)p2=(a2,b2)
(a1≤a2∧b1≥b2)
. 참고로 , P 1 과 P 2는 노 바꾸면 호환없는 그들 만이 경우두 스왑 호환(보낸 부분 위해 정의를 만족 P 1 ⪯ P 2 ≡ P * 2 ⪯ P * 1 , * 스왑 동작을 나타낸다) . 마지막으로, p 1 과 p 2 는정확히 하나가 교체 된 정렬 된 목록에서 순서대로 배치 될 수있는 경우하나의 교체가 가능합니다. 이것이 사실이라면 P * (1) 및
(a2≤a1∧b2≥b1)p1
p2
p1⪯p2≡p2∗⪯p1∗
∗
p1
p2
p1∗
는 스왑이 호환되지 않습니다. 나머지 경우 p 1 과 p 2 는 단순히 호환되지 않습니다. 스왑 상태에 관계없이 주문 조건을 충족시킬 수 없습니다.
p2p1
p2
이제 문제를 다음과 같이 해결할 수 있습니다. 모든 쌍을 테스트하십시오. 쌍이 호환되지 않으면 해결책이 없으므로 예외가 발생할 수 있습니다. 그렇지 않으면 원래 쌍에 해당하는 노드와 1 스왑 호환 되지 않는 노드 쌍 사이의 모서리가있는 그래프를 고려하십시오 . 이러한 각 노드 쌍은 올바르게 정렬 된 목록에서 동일한 스왑 상태를 가져야하므로 그래프의 연결된 각 구성 요소의 모든 노드는 동일한 스왑 상태를 가져야합니다. 이러한 구성 요소 전체 스왑 상태를 일관되게 할당 할 수 있는지 확인해야합니다. 연결된 각 구성 요소 내의 모든 노드 쌍을 테스트하십시오. 쌍이 호환되지 않는 쌍이면 해결책이 없으므로 예외가 발생할 수 있습니다. 이제 연결된 컴포넌트의 모든 쌍을 테스트합니다 (예 : 컴포넌트
C1그리고 , 모든 노드 쌍 p 1 ∈ C 1 및 p 2 ∈ C 2 )을 테스트합니다 . 우리는 각 구성 요소 쌍이 하나 이상의 스왑 호환 가능하다는 것을 알고 있지만 일부 쌍은 스왑 호환이 불가능할 수도 있습니다 (가장자리로 연결되지 않은 각 노드 쌍은 하나 이상의 스왑 호환 가능하기 때문에 스왑 호환 가능). 연결된 구성 요소에 해당하는 노드와 해당 구성 요소가 스왑이 호환 되지 않는 경우 두 노드 사이의 가장자리가있는 그래프를 줄 입니다. 이 그래프가 2 색인 경우에만 원래 문제에 대한 해결책이 있습니다. 2 가 없으면
C2p1∈C1
p2∈C2
2
2
-색칠, 해결책이 없으며 예외를 던질 수 있습니다. 하나가 있으면 단일 색상의 모든 구성 요소에있는 모든 노드를 교체하십시오. 이제 두 노드 모두 스왑이 호환되지 않으므로 정의 된 부분 순서를 사용하여 쌍 목록을 올바르게 정렬 할 수 있습니다.
알고리즘의 각 단계, 따라서 전체 알고리즘은 시간에 수행 될 수 있습니다 .
O(N2)업데이트 : 훨씬 더 우아한 구성은 다음과 같습니다. 한 쌍의 쌍이 스왑이 호환되지 않는 경우 해당 노드를 가장자리로 연결합니다 (2 색에서 다른 색이되도록 함). 한 쌍의 쌍이 1 스왑 호환이 아닌 경우, 해당 노드를 길이가 2 인 체인으로 연결하십시오 (2 색에서 동일한 색이되도록 함). 결과 그래프가 2 색인 경우에만 해결책이 있습니다. 그래프의 파란색-빨간색으로 솔루션을 구성하려면 해당 노드가 파란색 인 쌍만 교체 한 다음 결과 목록을 정렬하십시오.
답변
X (a, b)가 (a, b) 쌍을 교체해야하는지 여부를 나타내는 이진 변수를 나타냅니다. 별개의 쌍 (a, b) 및 (c, d)를 고려하고 두 쌍이있는 경우에만 만족되는 변수 X (a, b) 및 X (c, d)에 이진 제약 조건을 작성하십시오 X (a, b) 및 X (c, d)로 표시된 스왑을 수행 한 후의 올바른 순서. 이러한 모든 이진 제약 조건의 결합은 원래의 문제에 해결책이있는 경우에만 만족할 수있는 n 개의 변수와 O (n ^ 2) 절의 2-SAT 공식입니다. 시간 O (n ^ 2)에서 확인할 수 있습니다.
원래 솔루션의 경우 모든 제약 조건이 X (a, b) = X (c, d) 또는 X (a, b)! = X (c, d) (또는 그렇지 않으면 X (a, b) = 상수), 따라서 간단한 “이 분성 병합 및 확인”알고리즘이 작동합니다.
각 X는 자체 만 포함 된 세트의 대표로 시작합니다. X = Y가 구속 조건이되도록 모든 쌍 (X, Y)에 대해 X와 Y가 속하는 컴포넌트를 병합하십시오. 마지막으로 각 구성 요소가 하나의 정점이고 일부 경계가 관계 X! = Y가 보유해야하는 경우 X와 Y를 포함하는 구성 요소를 결합하는 계약 그래프가 이분인지 확인합니다.