숫자 쌍을 정렬하는 알고리즘 두 번째 숫자에

나는 이미 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_{1} = (a_{1}, b_{1})$

p_{1} = (a_{1}, b_{1})

$p_1=(a_1,b_1)$ $p_{2} = (a_{2}, b_{2})$

p_{2} = (a_{2}, b_{2})

$p_2=(a_2,b_2)$ $(a_{1} \leq a_{2} \land b_{1} \geq b_{2})$

(a_{1} \leq a_{2} \land b_{1} \geq b_{2})

$(a_1 \le a_2 \wedge b_1 \ge b_2)$ . 참고로 과 노 바꾸면 호환없는 그들 만이 경우두 스왑 호환(보낸 부분 위해 정의를 만족 , 스왑 동작을 나타낸다) . 마지막으로, 과 는정확히 하나가 교체 된 정렬 된 목록에서 순서대로 배치 될 수있는 경우하나의 교체가 가능합니다. 이것이 사실이라면 및 $(a_{2} \leq a_{1} \land b_{2} \geq b_{1})$

(a_{2} \leq a_{1} \land b_{2} \geq b_{1})

$(a_2 \le a_1 \wedge b_2 \ge b_1)$ $p_{1}$

p_{1}

$p_1$ $p_{2}$

p_{2}

$p_2$ $p_{1} ⪯ p_{2} \equiv p_{2}^{*} ⪯ p_{1}^{*}$

p_{1} ⪯ p_{2} \equiv p_{2}^{*} ⪯ p_{1}^{*}

$p_1 \preceq p_2 \equiv p_2^{*} \preceq p_1^{*}$ $*$

*

$*$ $p_{1}$

p_{1}

$p_1$ $p_{2}$

p_{2}

$p_2$ $p_{1}^{*}$

p_{1}^{*}

$p_1^{*}$ 는 스왑이 호환되지 않습니다. 나머지 경우 과 는 단순히 호환되지 않습니다. 스왑 상태에 관계없이 주문 조건을 충족시킬 수 없습니다. $p_{2}$

p_{2}

$p_2$ $p_{1}$

p_{1}

$p_1$ $p_{2}$

p_{2}

$p_2$

이제 문제를 다음과 같이 해결할 수 있습니다. 모든 쌍을 테스트하십시오. 쌍이 호환되지 않으면 해결책이 없으므로 예외가 발생할 수 있습니다. 그렇지 않으면 원래 쌍에 해당하는 노드와 1 스왑 호환 되지 않는 노드 쌍 사이의 모서리가있는 그래프를 고려하십시오 . 이러한 각 노드 쌍은 올바르게 정렬 된 목록에서 동일한 스왑 상태를 가져야하므로 그래프의 연결된 각 구성 요소의 모든 노드는 동일한 스왑 상태를 가져야합니다. 이러한 구성 요소 전체 스왑 상태를 일관되게 할당 할 수 있는지 확인해야합니다. 연결된 각 구성 요소 내의 모든 노드 쌍을 테스트하십시오. 쌍이 호환되지 않는 쌍이면 해결책이 없으므로 예외가 발생할 수 있습니다. 이제 연결된 컴포넌트의 모든 쌍을 테스트합니다 (예 : 컴포넌트 $C_{1}$

C_{1}

$C_1$ 그리고 , 모든 노드 쌍 및 )을 테스트합니다 . 우리는 각 구성 요소 쌍이 하나 이상의 스왑 호환 가능하다는 것을 알고 있지만 일부 쌍은 스왑 호환이 불가능할 수도 있습니다 (가장자리로 연결되지 않은 각 노드 쌍은 하나 이상의 스왑 호환 가능하기 때문에 스왑 호환 가능). 연결된 구성 요소에 해당하는 노드와 해당 구성 요소가 스왑이 호환 되지 않는 경우 두 노드 사이의 가장자리가있는 그래프를 줄 입니다. 이 그래프가 색인 경우에만 원래 문제에 대한 해결책이 있습니다. 가 없으면 $C_{2}$

C_{2}

$C_2$ $p_{1} \in C_{1}$

p_{1} \in C_{1}

$p_1 \in C_1$ $p_{2} \in C_{2}$

p_{2} \in C_{2}

$p_2 \in C_2$ $2$

2

$2$ $2$

2

$2$ -색칠, 해결책이 없으며 예외를 던질 수 있습니다. 하나가 있으면 단일 색상의 모든 구성 요소에있는 모든 노드를 교체하십시오. 이제 두 노드 모두 스왑이 호환되지 않으므로 정의 된 부분 순서를 사용하여 쌍 목록을 올바르게 정렬 할 수 있습니다.

알고리즘의 각 단계, 따라서 전체 알고리즘은 시간에 수행 될 수 있습니다 . $O (N^{2})$

O (N^{2})

$O(N^2)$

업데이트 : 훨씬 더 우아한 구성은 다음과 같습니다. 한 쌍의 쌍이 스왑이 호환되지 않는 경우 해당 노드를 가장자리로 연결합니다 (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를 포함하는 구성 요소를 결합하는 계약 그래프가 이분인지 확인합니다.

How IT

언제든지 물어보세요.

숫자 쌍을 정렬하는 알고리즘 두 번째 숫자에

답변

답변

답변