順列の圧縮列挙索引化とソーティング

川原　純; 湊　真一

あらまし

順列の圧縮列挙索引化とソーティング

川原　純湊　真一

Vol.97 No.12pp.1086-1090

発行日:2014/12/01

Online ISSN:2188-2355

Print ISSN:0913-5693

種別:小特集　「フカシギの数え方」から広がるアルゴリズムの理工学――二分決定グラフによる離散構造処理と広がる応用分野――

専門分野:

キーワード:
πDD, ZDD, 順列, ルービックキューブ, あみだくじ,

本文:PDF(435.6KB)>>

あらまし:
基礎的な離散構造の一つである順列（置換）は，ソーティングや順序付け，マッチング，レイアウト，符号化等，多くの実用的な問題で現れる．近年提案されたπDDは，多数の順列の集合を圧縮された状態で保持するデータ構造であり，二つの順列集合の和集合や共通集合を求める演算，二つの順列集合から任意に要素を取り出して積をとって得られる集合の計算等，各種集合演算をサポートする．本稿では，ルービックキューブの最小手順の計算やあみだくじの線の引き方の数え上げを題材に，πDDの基礎的な事柄について解説し，順列集合の演算の威力を見ていく．

あらまし

ログイン

メニュー