順列の目録

最近トップコーダーのアルゴリズム問題を解いた時には騙されました。最初に木構造を作成した。これは順番を現しました。次は状態空間に深さ優先探索で順列を述べました。一つな順列を完成した時に快適さを確認します。A simple approach to solving this would be to enumerate all permutations of non-entry permutations using the Pandita lexicographic permutations algorithm, then to check each permutation such that no room is placed before any of its predecessors. This is roughly O(n!*n^2) in complexity. Another possibility for "in-place" permutation constraint checking is to check each room placed in a permutation such that it is not being placed after any room it is a predecessor of (requires a successors data structure mapping an element to a list of elements it precedes, based on the tree structure). Note that the tree is read into memory from a list of edges and a root node denoted as the "entrance".