2

複数の順序付きリストがあります。残念ながら、アイテムの順序は単純なアルファまたは数値の比較ではありません。だから私が持っているのは次のようなものです:

List #1        List #2       List #3
groundhog      groundhog     easter
mothersday     mayday        mothersday
midsummer      laborday      halloween
christmas

そして、このことからグラウンドホッグ＜マザーズデイよりも集められるのですが、グラウンドホッグとイースターの関係は不明です。リストからリストへのアイテムの順序が一貫していることを保証します。(つまり、どのリストに含まれていても、イースターは常にハロウィーンの前です)

しかし、私が必要としているのは、他のリストの各項目を 1 回だけ表す新しい順序付きリストであり、上記の既知の関係がすべて保持されます。

groundhog
easter
mayday
mothersday
midsummer
laborday
halloween
christmas

ただし、次のリストも完全に有効です。

easter
groundhog
mothersday
mayday
midsummer
laborday
halloween
christmas

この方法で N 個のリストを並べ替えるために使用できる、かなり高速な汎用アルゴリズムを探しています。(動作する C# コードは確かにプラスですが、必須ではありません。)

私はうまくいく解決策を持っていますが、その O(N^2) と適度なデータセットを持つ犬です。

4

3 に答える 3

5

トポロジカル ソートを参照してください。あなたのケースにとてもよく当てはまると思います。

于 2008-11-11T21:52:50.070 に答える
1

@bdumitriuに同意します。トポロジカルソートが必要です。

このタイプの並べ替えでは、データ項目間に部分的な順序があることを前提としています。つまり、特定の項目のペアについて、それらを比較して、どちらが先行しているかを確認できます。この場合、あなたが言うように、すべての制約を保持するアイテムの単一のリストを作成する方法は複数あります。

トポロジカル ソートは通常、最初にアイテムの有向非巡回グラフを作成することで機能します。ここで、各アイテムが頂点になり、ノード X からノード Y への有向エッジは、入力リストでアイテム X がアイテム Y より前にあることを意味します。(したがって、一連の入力ソート済みリストをウォークスルーし、新しいアイテムに遭遇するたびに、その頂点を作成し、各ソート済みリスト内の連続するアイテムのペアごとに、からの有向エッジを作成します。最初の項目から 2 番目の項目へ. 各入力リストの項目から前のすべての項目への有向辺を作成する必要がないことに注意してください. たとえば, 入力リスト 1 では, 辺groundhog-> mothersday, mothersday->を作成します. midsummer、およびmidsummer-> christmas.)

トポロジカル ソートには O(V+E) の時間がかかります。ここで、V はソートするアイテムの総数 (頂点の数) であり、E は入力リストからの先行関係の総数 (エッジの数) です。 .

――フィル

于 2008-11-17T22:28:46.697 に答える
0

私なら Array.Sort メソッドを使用し、比較する 2 つの文字列を取得して任意のリストに存在するかどうかをチェックする Comparison メソッドを使用します。それらの両方を含むリストは、それらの相対的な位置を見つけ、それに基づいて返されます。リストに両方が含まれていない場合は、等価を返します。

MSN のドキュメントには、ソート アルゴリズムでクイックソートが使用されていると記載されています。nlog(n) オーダーの平均化。最悪の場合は n^2 オーダーです。

このようにして、ソートアルゴリズムの実装を活用できます。比較コードを実装するだけです。

于 2008-11-11T22:56:36.120 に答える