問題タブ [poset]

次のアルゴリズムの時間計算量を改善するのを手伝ってください。

ハッセ図（ハッセ図とは何かをすでに知っている場合は、このセクションをスキップしてください。次のセクションに直接進んでください）：

半順序集合（略してポーズ）（A、⊆）を考えます。ここで、Aは集合であり、⊆半順序です。図の各ノードは半順序集合の要素であり、2つの要素xとyが線で接続されている場合、x⊆yまたはy⊆xです。要素の位置と接続は、次のルールに従って描画されます。

1. 半順序集合でx⊆yの場合、xに対応する点はyに対応する点の下に表示されます。

2. ポセットの推移性はグラフィカルに省略されます。つまり、x⊆yおよびy⊆zの場合、半順序⊆、x⊆zの推移性によって省略されます。この場合、接続xzは省略されます。

3. 同様に、再帰性はグラフィカルに省略されています。

Poset（S = {{1,2,3,5}、{2,3}、{5}、{3}、{1,3}、{1,5}}、⊆）のハッセ図表現は次のように（エッジのみが報告されます）

{1,2,3,5}-> {2,3}

{1,2,3,5}-> {1,3}

{1,2,3,5}-> {1,5}

{2,3}-> {3}

{1,3}-> {3}

{1,5}-> {5}

私の最初の考え

私が考えることができる唯一のアルゴリズムは、次のようにO（N ^ 2）です。

最初の要素がSであることを読み取り、ハッセ図の最初の要素として挿入します。次の要素を読むとき、それらをすでに作成された図の正しい位置に挿入します（これまでに作成された図にK個の要素があるとすると、新しい要素を正しい場所に挿入するにはO（K）時間がかかります）。このようにして、O（N ^ 2）は明らかです。

しかし、ポセットSの要素を並べ替えることが役立つかどうかを考えていますが、⊆がすべての要素のペアに当てはまらない可能性があるため、Sの完全な要素の並べ替え順序を作成することはできません（例、{2,3}と{1,3を検討してください） }）。

最悪の場合の複雑さを改善するためのアイデアは大歓迎です!!

ありがとう。

PS：これは宿題の問題ではありません!!

半順序が定義されている要素のコレクションを保持し、トポロジカル順序でそれらの要素を反復できるデータ構造のJava実装を探しています（可能な順序はどれでも問題ありません。できれば安定しています）。コレクションの内容が変更されたときの順序）。

理想的には、、、、またはインターフェイスを実装し、インターフェイス上のすべてのメソッドをサポートしますCollection<E>。全体の順序を指定するという点では、コレクションは。でインスタンス化でき、比較対象の2つの要素が相互に順序付けされていない場合、コンパレータは例外（？）をスローする可能性があります。ボーナスとして、挿入されている要素が順序異常（要素の順序グラフのサイクル）を生成する場合、例外がスローされます。Set<E>SortedSet<E>Comparator<E>ClassCastException

そうですね、トポロジカルソートが必要ですが、SortedSetがコレクションをソートされた順序で維持するのと同様に、挿入/削除のたびにそのソート順を維持するコレクションオブジェクトが必要です。

このようなものはありますか？いくつかのオープンソースライブラリでは？

参照：

http://en.wikipedia.org/wiki/Partially_ordered_set

http://en.wikipedia.org/wiki/Topological_sorting

アップデート

要件のパフォーマンスへの影響（および、ポセットを使用して完全に解決できなかった他のさまざまな問題）を認識した後、ポセットを必要としないという別のアプローチを採用することになりました。要素間の順序を決定するためにコンパレータに依存するということは、要素の挿入については、既存のすべての要素に対してコンパレータを参照する必要があり、挿入ごとにO（n）のコストがかかることを意味します。

パフォーマンスがそれほど重要ではなく（そうである場合）、要素の数が合理的なものに制限されている場合（そうではない）、おそらく私自身のグラフの実装とトポロジカルを使用して、ウィリーによって提案されたアプローチを採用したと思います依存関係を最小限に抑えるために実装をソートします。

私は部分的に順序付けられたセット、たとえば を持っていますA = [x1, x2, ...]。つまり、セット内の各xiおよびについてxj、(正確に) 4 つの可能性のうちの 1 つが真です: xi < xj、xi == xj、、xi > xjまたはは比類のないものです。xixj

xi最大の要素 (つまり、 の要素がない要素)xjを見つけたいと考えていますxi < xj。これを行うための効率的なアルゴリズムは何ですか (比較の数を最小限に抑えます)? DAG を構築してトポロジカル ソートを実行しようとしましたが、グラフを構築するだけでも O(n^2) の比較が必要であり、これは多すぎます。

私はこれを Python で行っていますが、それがわからない場合は、他の言語または疑似コードを読むことができます。

ステートメントのブロックを使用する手続き型 EDSL があります。

これらのステートメントは、特定の順序でブロックに追加されませんが、ステートメント間に依存関係がある場合があります。

ただし、EDSL のコンパイル中は、ステートメントが依存の順序で並べられていることを確認する必要があります。

すべてのステートメントに依存関係があるわけではないため、完全な順序はありません (たとえばE := D、上記は独立しており、どこにでも配置できます)。循環的な依存関係がないため、リストの順序付けが可能になるはずです。

ステートメントに依存関係がないことを意味するwhich を使用Data.List.sortByして定義することにより、ソリューションをハックしようとしました。これはいくつかの例では機能しましたが、一般的なケースでは機能しませんでした。たとえば、次の順序で何もしませんでした:OrderingEQ

これは、デフォルトの並べ替え挿入並べ替えが、挿入されたアイテムが次のものより小さいか等しいことを確認するためです。

インターネットでPosetの実装を検索しましたが、該当するものは見つかりませんでした:

altfloat:Data.PosetはOrdering = LT | GT | EQ | NC( NCNon-comparable の場合) を定義しますが、提供されたものは-like非比較項目をsort想定し、単にそれらを破棄します。NaN

logfloat:Data.Number.PartialOrdは、使用法を除いて上記と似ておりMaybe Ordering、パッケージのどこにもソート機能がありませんでした。

Math.Combinatorics.Poset使用方法や適用可能かどうかはわかりません。

以下は、拘束力のあるステートメントと拘束力のないステートメントの両方を持つ最小限の例です。非バインド ステートメントの順序は重要であり、それらは元の順序を維持する必要があります (つまり、並べ替えは、依存関係を持たない wrt ステートメントに対して安定している必要があります)。

本格的な依存グラフを使用せずに、これに対する簡単な解決策があることを願っています...

特定のposetの最大アンチチェーンを計算しようとしています。次のメソッドを作成しました。

aこれは、2 つのノードが比較できない場合 (つまり、 fromにb も frombにもパスがない場合) にのみ true を返しますa。

LinkedHashMap を定義しました

これは、すべてのノード N をその比類のない要素にマップしますIncomp(N)。

例: 要素が {A,B,C,D} で、A>B、A>C、D>C の関係があるとします。

重複は許可されていないことに注意してください (つまりIncomp(C)={B}、(B,C) が含まれIncomp(B)ているため、繰り返す必要はありません)。

私はここで立ち往生しています。要素間の不一致をチェックIncomp(N)してから、最大アンチチェーンとして最大サイズのキーを取得する必要がありますか? つまり、この設定で最大のアンチチェーンを見つける方法は?

これは非効率になるため、サイズ k のすべてのサブセットを生成することはできません。

モジュールの配列が与えられた場合、モジュール間の正規化された (最小限の) 順序関係を記述する配列を返す最良の方法は何ですか? 配列の各要素は、親子関係を持つモジュールのペアの配列でなければなりません。各ペア内の親子の順序は重要ですが、ペア間の順序は重要ではありません。正規化された順序付けとは、推移性から派生できるものはすべて配列から除外する必要があることを意味します。

たとえば、 が与えられた[Object, Comparable, Float, Fixnum, Integer]場合、答えは次のようになります。

配列内の 5 つのペアは、次のハッセ図の 5 つのエッジに対応します。

ヒント:順序関係がある場合は 、順序関係がない場合はをModule#<=>other返します。-101nil