정렬 된 하위 목록을 정렬 된 수퍼리스트에 병합

Question

각각 m 개의 요소 (문자열)가있는 n 개의 정렬 된 목록의 목록이 있습니다. 이러한 요소는 내가 모르는 별개의 순서로 List에서 유래했습니다. 내가 아는 것은 모든 하위 목록이 요소의 전역 질서를 유지한다는 것입니다. 목록은 분리되어 있지 않습니다. 목록의 합집합은 원래 목록의 하위 집합입니다.

지금 나는 최대 정렬 정확도를 가진 목록 (목록)으로 효율적으로 다시 결합하는 알고리즘을 찾기 위해 고심하고 있습니다.

이러한 문제에 대한 해결 방법이 있습니까?

List<List<String>> elements = new ArrayList<>(); 

elements.add(Lists.newArrayList("A","D","F")); 
elements.add(Lists.newArrayList("B","D","E")); 
elements.add(Lists.newArrayList("A","B","G")); 
elements.add(Lists.newArrayList("C","D","H")); 

// the required method 
List<List<String>> sorted = sortElements(elements); 

/* expeced output: 
* [["A"],["B"],["C"],["D"],["G","F","E","H"]] 
*/ 

Answer 1

당신은 topological sorting 찾고 있습니다 : 나는 자바를 사용하고

, 여기에 몇 가지 예제 코드입니다.

되는 초기리스트 그래프 호 관한 표현한다 (A-> D, D-> F 등)

P.S. 레벨별로 노드를 명시 적으로 나누기위한 특수한 종류의 토폴로지 정렬은 러시아 문학 "Demoucron 알고리즘"에서 호출되지만 적절한 영어 설명 (평면 그래프 드로잉 기사에 대한 링크를 찾았습니다)을 찾지 못했습니다.

예제 :