algorithm - 半順序リストを並べ替える最良の方法は何ですか？

Question

おそらく、小さな例で最もよく説明されています。
関係を考えると

A < B < C
A < P < Q 

正しい出力は

ABCPQ or APQBC or APBCQ ... etc.

つまり、特定の関係が成立する順序はすべて有効です。

実装が最も簡単なソリューションに最も興味がありますが、速度と時間の点で最高のO（n）も興味深いものです。

Answer 1

これはトポロジー ソーティングと呼ばれます。

標準的なアルゴリズムでは、最小限の要素を出力してから削除し、完了するまで繰り返します。

Answer 2

いくつかの並べ替えを行います。最初に最初のルールに従ってソートし、次に 2 番目のルールに従ってソートします。ルールに矛盾が含まれていない限り、機能するはずです。簡単に実装できます。

Answer 3

手元にあるシーケンスを使用して、C++ で make_heap、pop_heap を繰り返し呼び出すことができます。