問題タブ [poset]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
python - 部分順序集合を通過する方法の数
これは、以前の質問Solve a simplepackcombination with dependenciesに基づいていますが、これを理解するためにその質問をチェックアウトする必要はありません。
この質問は、部分的に順序付けられたセットの線形拡張の数を数える最速の方法について尋ねます。
このような部分的に順序付けられたリストは、オブジェクトの任意の順序が与えられた場合のパッキング構成の実現可能性として視覚化できます。質問は、配置されたブロックを移動できない場合、示されているパッキング構成を実現するために、渡されたすべてのブロックの可能な順序は何ですか?
この例では、すべてのブロック ABCDEFG を配置する必要があります。A、B、C、D の依存関係: set{}、E: set{A,B}、F: set{B,C} G: set{C、 D}。
7 つのブロックのすべての順列をチェックし、依存関係を満たす数を数えることで、部分的に順序付けられたセットを完成させる可能性をすべて得ることができます。以前の投稿の גלעד ברקן によって、より高速な代替手段が提供されました。彼は、既に探索されたノードで依存関係が満たされない場合、ブランチへのさらなる探索を終了するグラフ構造を使用しました。
私の質問は、一般性を失うことなく גלעד ברקן のアルゴリズムをさらに最適化する方法があるかどうかということです。依存関係が少なく、リストを独立したサブリストにさらに分割できる場合は、おそらく高速化できますが、この特定の例ではそうではありません。