ハイパーキューブ上の順列の同形を反復しない網羅的生成

• Item type: SIG Technical Reports(1)
• 公開日: 2000-11-10
• タイトル: ハイパーキューブ上の順列の同形を反復しない網羅的生成
• タイトル / 言語: en
• タイトル: Isomorph - free exhaustive generation of permutations on the hypercube
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 明治大学大学院理工学研究科
• 著者所属: 明治大学大学院理工学研究科
• 著者所属(英): en
• 著者所属(英): School of Sience and Technology, Meiji University
• 著者所属(英): en
• 著者所属(英): School of Sience and Technology, Meiji University
• 著者名: 藤井, 俊一; 玉木, 久夫
• 著者名(英): Toshikazu, Fujii; Hisao, Tamaki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ハイパーキューブ上の順列のすべてを、同形を反復することなく生成する問題を考える。部分順列の正規形を適当に定義すると正規形の部分順列全体の集合が、正規形の順列を葉に持つ木を構成することを示す。我々の生成アルゴリズムはこの木に対して深さ優先探索を行なう。このアルゴリズムの生成速度は正規形判定に要する時間に大きく依存している。正規形判定の効率化の手法を開発し、実験により4次元のキューブに対して素朴な方法の約11倍の生成速度が得られることを示す。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We consider the problem of generating all permutations on the hypercube without repeating isomorphs. We show that, with an appropriate definition of the canonical forms of partial permutations, the set of all canonical partial permutations forms a tree in which canonical permutations are placed on the leaves. Our generation algorithm simply performs a depth first search on this tree. The generation speed of the algorithm depends heavily on the efficiency of the algorithm that decides if a given partial permutation is canonical. We develop techniques for efficiently deciding canonicality and experimentally show that an improvement by a factor of nearly 11 is achieved for the 4-dimensional cube over the naive method.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2000, 号 103(2000-AL-075), p. 69-73, 発行日 2000-11-10
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会