algorithm - 任意の 2 つの数値間の二項関係が与えられた場合の n 個のオブジェクトの並べ替え

Question

問題文: n 個のオブジェクト a1,a2...an を並べ替え、任意の 2 つの数の間に 2 項関係が与えられている場合。

たとえば、5 つのオブジェクト a1、a2、a3、a4、および a5 について説明します。

a1 < a5
a4 < a2
a3 < a5
a2 < a1
a1 < a3

したがって、順序は次のようになります a4 a2 a1 a3 a5 これを行うアルゴリズム

Answer 1

簡単な方法は、行列を保持し、relationships[x, y] = true if x < yその行列をお気に入りの並べ替えアルゴリズムの比較関数として使用することです。

ただし、トポロジカルソートはおそらくより効率的です。