C 또는 Python의 효율적인 알고리즘은 두 숫자 사이의 관계를 나타내는 순서가 지정되지 않은 쌍의 목록이 주어질 때 쌍을 결합하여 연속 된 명부. 이들의 쌍의 틈새 나 루프가있는 곳 분명히Python 또는 C : 쌍 목록을 연결된 목록으로 바꾸기
[0, 1, 2, 3, 4]는,이 작동하지 않을 것, 예를 들어, (0, 1) (3, 4), 그리고 :
(0, 1)
(1, 2)
(3, 2)
(4, 3)
는 다음과 같은 생산 : 다음 주어진 예를 들어
, 오류 메시지 나 비슷한 것을 던져라.
숫자는 그래프의 꼭지점으로 모델링 할 수 있습니다. 목록의 각 요소는 노드 사이의 모서리를 나타냅니다.
당신이 찾고있는 것이이 그래프의 '오일러 경로'입니다. 이를위한 여러 가지 알고리즘이 있습니다. http://en.wikipedia.org/wiki/Eulerian_path
하려고하는 것은 (각 가장자리를 한 번 방문하는) Eulerian 경로가 아니지만 Hamiltonian path (각 꼭지점을 한 번 방문 함)입니다. 왜냐하면 루프에서 루프를 사용하지 않으려 고하기 때문입니다. 경로의 정의에 의해 어떤 꼭지점을 두 번 방문하고 싶지 않다는 것을 의미합니다.
이 문제는 NP-complete으로 알려져 있습니다. 이는 알려진 효율적인 알고리즘이 없다는 것을 의미합니다 (polynomial time을 "효율적으로"사용하는 경우).
이 문제에 대한 효율적인 알고리즘을 찾을 수 있으면 P와 NP가 동일하다는 것을 보여줌으로써 P vs NP problem도 풀 수 있습니다. 대부분의 컴퓨터 과학자들은 P 대 NP 문제에 대한 대답은 "아니요, NP 문제에 대한 효율적인 알고리즘은 불가능합니다"라고 믿습니다. 즉, 귀하의 질문에 대한 효율적인 알고리즘의 가능성은 없다는 것을 의미합니다.
무엇이 질문입니까? – Blender
기본적으로 배열을 병합하고 중복을 제거 하시겠습니까? – Havenard
아니요, 목록의 순서는 원래 쌍을 기준으로합니다. – speedplane