セットの大規模なコレクションがあり、そのうちのいくつかは互いにサブセットです。
[{1, 2, 3, 4}, {1, 2}, {1, 5}, {1, 2, 3, 4, 5}, {2, 6}]
このコレクションを取得して、サブセット関係の半順序の DAG を出力したいと思います
{1, 2, 3, 4, 5} >= {1, 2, 3, 4} >= {1, 2}
{1, 2, 3, 4, 5} >= {1, 5}
{2, 6}
セットのすべての組み合わせを比較する以外にこれを行う方法はありますか (これは、多数のセットがある場合は禁止されています)。これは多くのセット カバーの問題に近いようですが、これが減少する問題は見つかりません。
{2, 6}最適化の 1 つは、とのような共通要素を持たないセットの比較を避けるのに役立つ逆インデックスを作成すること{1, 5}です。
この問題は、位相ソートと半順序の線形拡張に関連しているようです。
これは、厳密関数型プログラミングを使用してポーズセットから DAG を生成するのほぼ複製ですが、純粋に関数型ではないソリューションを受け入れます。