問題タブ [partial-ordering]

セットの大規模なコレクションがあり、そのうちのいくつかは互いにサブセットです。

このコレクションを取得して、サブセット関係の半順序の DAG を出力したいと思います

セットのすべての組み合わせを比較する以外にこれを行う方法はありますか (これは、多数のセットがある場合は禁止されています)。これは多くのセット カバーの問題に近いようですが、これが減少する問題は見つかりません。

{2, 6}最適化の 1 つは、とのような共通要素を持たないセットの比較を避けるのに役立つ逆インデックスを作成すること{1, 5}です。

この問題は、位相ソートと半順序の線形拡張に関連しているようです。

これは、厳密関数型プログラミングを使用してポーズセットから DAG を生成するのほぼ複製ですが、純粋に関数型ではないソリューションを受け入れます。

Sタイプの要素のセットがありますT。<=type の要素には半順序がありTます。のすべての要素Sが順序付けされていないことが知られています。次に、次のクエリを実行する方法が必要ですeTe'Se <= e'。

そのようなクエリを効率的に実行できるデータ構造はありますか (の線形スキャンなしS)?

重要な注意:T完全な格子です。