부분 순서 집합에서 시퀀스를 재구성

나는 한 쌍의 요소 쌍을 가지고 있습니다. 각 쌍의 의미는 다음과 같습니다. 마지막 시퀀스에서 첫 번째 요소는 두 번째 요소 인 앞에옵니다. 쌍 세트에는 고유 한 순서를 재구성하기에 충분한 쌍이 들어 있습니다.부분 순서 집합에서 시퀀스를 재구성

예 : :

쌍 내 세트 A는 B에 선행 {(A, B), (A, C), (C, B)}에게

= 인 경우, A는 C 및 C가 B 앞에 선행.

최종 시퀀스는 ACB입니다.

이제이 종류의 쌍 집합에서 시퀀스를 재구성하는 알고리즘이 필요합니다. 효율성이 중요합니다. 모든 스마트 팁을 환영합니다!

2011-02-11 Ben

그리고 이것은 수업 중 숙제입니까? –

@Henk, 이것은 실제 응용 프로그램에 대한 문제입니다. – Ben

그냥 프로빙. 너무 많이 일반화하면 운동처럼 보이기 시작할 수 있습니다. –

이러한 쌍에서 유향 그래프를 만든 다음 topological sort을 수행하십시오.

2011-02-11 13:49:53 kennytm

첫 번째로 +1하십시오.) –

다음은 알고리즘 요약에 대한 참고 자료로, 많은 구현에 대한 포인터가 있습니다. http://www.cs.sunysb.edu/~algorith/files/topological-sorting.shtml – payne

이것은 지향 그래프의 위상 정렬 문제입니다. Read More

2011-02-11 13:50:29

답변