順列のサイクルタイプ同値類分割に対する順列決定グラフの適用
Applying Permutation Decision Diagrams to Cycle type Partition
on a Permutation Set
井上 祐馬
1∗湊 真一
1Yuma Inoue
1Shin-ichi Minato
1,21
北海道大学大学院情報科学研究科
1
Graduate School of Information Science and Technology, Hokkaido University
Abstract: Permutations are discrete structure appearing in several mathematical and practical problems such as scheduling, ranking, and matching. Cycle type of a permutation is one of notions characterizing the permutation in terms of bijection and group action. In this paper, we apply a compressed data structure for permutation sets, permutation decision diagram (πDD), to compactly represent permutation set partitions based on cycle type, and propose a new algorithm efficiently constructingπDDs in bottom-up manner. Computational experiments show our method is faster and less memory usage than an existing method.
1
はじめに
1.1
研究背景
現実問題によく現れる重要な離散構造の一つとして 順列がある．順列とはモノの並び方を表す列であり，ス ケジューリングやルーティング，ランキングなどの問 題に現れる．また，{1,...,n} の各要素を持つ長さ n の 順列は全単射関数だと考えることができるため，マッ チングや符号化などの問題にも関連する． 順列の特徴づけの一つに，サイクルタイプがある．詳 細な定義は 2 節で行うが，順列は図 1 のように独立し た複数のサイクルからなるグラフの形で書くこともで き，このとき各長さのサイクルをそれぞれいくつずつ 持つかがサイクルタイプに対応する． 順列集合が与えられたとき，その順列集合にどのサ イクルタイプの順列がいくつ含まれているか調べるこ とは様々な応用を持つ．例えば，順列集合に含まれる 順列それぞれのサイクルタイプを利用して得られる多 項式は，ポリアの数え上げ定理にも用いられる母関数 を与える [4]．また，順列のサイクルタイプから順列の 周期が計算できるが，順列の周期が計算量に影響する アルゴリズムに関して，入力として想定される順列集 合の各サイクルタイプの分布を知ることは，アルゴリ ズムの平均時解析を行うために有用である．このよう に，順列集合に各サイクルタイプの順列がいくつ含ま れているかは，その順列集合の数理的な特徴を明らか ∗連絡先： 北海道大学大学院情報科学研究科 060-0814 札幌市北区北 14 条西 9 丁目 E-mail: [email protected] にする上で基礎的かつ重要な情報となる． サイクルタイプが同じ順列同士に同値関係を定義す ることで，順列集合は同値類に分割できる．これをサ イクルタイプ同値類分割という．与えられた順列集合 に対し，サイクルタイプ同値類分割を求めることがで きれば，前述のサイクルタイプの分布はもちろん，よ り詳細な分析が可能となる．1.2
本研究の目的
本研究の目的は，入力として与えられた順列集合に 対し，そのサイクルタイプ同値類分割を計算すること である．順列のサイクルタイプを求めるための計算は その長さに対し線形時間で行えるため，順列集合がメ モリに納まる場合は 1 つずつ処理していくことも考え られる．しかし，順列の特徴のみが指定されていたり， その生成元のみが知られているが，実際の順列集合は 膨大で取り扱いが困難である場合も考えられる．その ような場合の解決策として，特定の順列集合を圧縮表 現して取り扱うことが考えられる． 本研究では順列を圧縮表現するためのデータ構造と して，順列決定グラフ (πDD) [3]を用いる．πDDは順 列の集合を効率的に保持するだけでなく，条件付き絞 り込みや 2 つの集合間の共通集合の計算などを解凍す ることなく行えるため，効率的な操作も提供できると いう点で，後の様々な応用のために優れている． また，例えば相対位置関係など，特定の制約を与え た順列集合を表すπDDをその条件のみから構築する手 法 [1] がすでに研究されているため，順列集合の特徴 人工知能学会研究会資料 SIG-FPAI-504-09がこのような制約の枠組みに入る場合，前述の圧縮表 現した入力として与えることが比較的容易である． よって本研究では，与えられた順列集合を表すπDD に対し，サイクルタイプ同値類それぞれを表すπDDの 集合を求める効率的な手法を設計することを目指す．
1.3
本研究の貢献
与えられた順列集合に対するサイクルタイプ同値類 分割にπDDを用いた先行研究がある [5]．本研究の提 案手法は，下記の観点で先行研究の問題点を改善して いると言える． • 既存手法ではどのような順列集合が入力であって も，その集合が持つ順列の長さ n に対し，長さ n の全順列に関する計算を必要とする．一方，提案 手法では，入力となる順列集合に対応するπDD を基にして計算を行うため，πDDで効率的に圧 縮可能な入力に対して高速に動作することが期待 できる． • 既存手法では最終的な出力に関係のないπDDを 多く生成してしまうが，それに比べ提案手法は冗 長なπDDの生成が抑えられている． • 5 節で示されるように，計算機実験の結果，提案 手法の方が高速・省メモリである．具体的には約 20倍高速で，約 5 倍省メモリである．1.4
本論文の構成
2節で，本研究で扱う対象となる順列やそのサイクル タイプ，サイクルタイプ同値類を定義する．続く 3 節 では，本研究で利用するデータ構造・順列決定グラフ (πDD)を導入する．4 節にて既存手法と，本研究にお ける提案手法を示した後，5 節にて計算機実験の結果 を用いて 2 つの手法を比較評価する．最後に 6 節でま とめと今後の課題について述べる．2
順列とサイクル分解
本節では，本稿で取り扱う順列とサイクル分解，お よびサイクル分解に基づく同値類の定義とその同値類 分割を定義する．2.1
順列
長さ n の順列とは，1 から n までの整数がちょうど 1 回ずつ現れるような数列である．すなわち，順列πππを 6 5 4 1 2 3 図 1: 順列 (4, 6, 1, 3, 5, 2) を表す有向グラフ πππ= (π1,π2, . . . ,πn)と表記するとき，以下の 2 条件を満 たす． • 1 ≤ i ≤ n について，πi∈ {1,2,...,n} • i ̸= j ⇔πi̸=πj また，順列πππ= (π1,π2, . . . ,πn)は，πππ(i) =πiで定義 される全単射関数，すなわち置換を表している，と捉 えられる．すべての i についてπi= iを満たすπππを恒 等置換とよび，eeenと書く．置換 aaa, bbbの合成を， aaa(bbb) = (aaa(bbb(1)), aaa(bbb(2)), . . . , aaa(bbb(n)))
= (ab1, ab2, . . . , abn)
と定義する．これを順列の積とも呼ぶ．順列の積の演 算は可換とは限らない．
a a
a(bbb) = bbb(aaa) = eeenとなる bbbを aaaの逆置換といい，aaa−1 とも書く． 長さ n の順列全体の集合を Snと書く．Snは上記の積 演算について群をなすことが知られており，この群は 対称群と呼ばれる．
2.2
サイクル分解
長さ n の順列πππについて，i 番目の要素がπiならば i からπiへの辺を引くことで，頂点数 n，辺数 n の有向グ ラフが得られる．例えば，順列 (4, 6, 1, 3, 5, 2) に対する 有向グラフは，図 1 のようになる．この有向グラフはど の頂点に関しても入次数，出次数がともにちょうど 1 で あることから，いくつかのサイクルから構成されるこ とがわかる．よって，任意の順列πππはいくつかのサイク ルに分解することができ，分解されたサイクルの集合を πππのサイクル分解と呼ぶ．ここで，a→ b → ··· → z → a というサイクルを (ab . . . z) と書くことにすると，例え ば順列 (4, 6, 1, 3, 5, 2) は (5)(26)(143) と書くことがで き，これをサイクル分解表記という．2.3
サイクルタイプと同値類分割
順列πππのサイクルタイプとは，πππのサイクル分解にど の長さのサイクルがいくつ含まれているかによって定義される．より形式的には，πππのサイクルタイプ ccc(πππ)∈ Nn は，i 番目の要素がπππのサイクル分解に含まれる長さ i のサイクルの個数を表すような n 次元の整数ベクトル である．例えば順列 (4, 6, 1, 3, 5, 2) = (5)(26)(143) のサ イクルタイプは (1, 1, 1, 0, 0, 0) となる． サイクルタイプにより，2 つの順列間に同値関係を定 義することができる．2 つの順列πππとρρρがサイクルタイ プ同値であるとは，2 つの順列のサイクルタイプが一致 すること，すなわち ccc(πππ) = ccc(ρρρ)であることをいう．例 えば，(4, 6, 1, 3, 5, 2) = (5)(26)(143) と (1, 4, 6, 2, 3, 5) = (1)(24)(365)はサイクルタイプ同値である．この同値 関係に基づいて定義された同値類をサイクルタイプ同 値類と呼ぶ． 本研究の目的は与えられた順列集合に対して，サイ クルタイプ同値類への分割を行い，同値類の集合を求 めることである．
3
順列決定グラフ
順列決定グラフ (πDD) [3]は順列の集合を圧縮して 表現するデータ構造である．本研究ではこのデータ構 造を用いて入力，および出力の順列集合を表現・操作 することで効率的なアルゴリズムの設計を行う．順列 決定グラフの導入のために，まず順列の互換分解の概 念を導入する．3.1
順列の互換分解
2つの要素を除き恒等写像となるような置換は特別 に互換と呼ばれる．2 つの要素が i と j(i < j) である とき，この互換をτi, jと表記する．任意の置換πππは互 換のみからなる積で表せることが知られている．特に， πππから恒等置換を作るために，大きい添字の要素から 順に揃えていくよう互換を適用する列を考えることで， n−1 個以下の一意な互換の列で表せる．このような置 換の互換列への分解を互換分解と呼ぶ．具体的には，k を n から 2 へと降順に動かしていき，k ステップ目では k番目の要素πkと k とを交換する互換τπk,kを適用す る．ただし，πk= kの場合は互換は適用しない．例えば， (4, 6, 1, 3, 5, 2)を互換の積の形で表す場合，6 番目にあ る 2 を 6 と交換するようτ2,6を適用し，(4, 2, 1, 3, 5, 6) となる．次に 5 番目はすでに 5 なので無視し，4 番目に ある 3 を 4 と交換するようτ3,4を適用し，(3, 2, 1, 4, 5, 6) となる．最後に 3 番目にある 1 を 3 と交換するようτ1,3 を適用すると，(1, 2, 3, 4, 5, 6) となり，恒等置換となる． よって，(4, 6, 1, 3, 5, 2) はτ2,6τ3,4τ1,3と互換の列で表せ る．逆に，恒等置換にこの互換の列を逆順に適用する と，分解前の置換が得られる．𝑓
x
𝑓
1 Jump 0 0𝑓
0x
𝑓
0𝑓
1𝑓
1x
x
0 1 0 1 0 1 等価な節点の共有 冗長な節点の削除 図 2: 2 つの圧縮ルール1
1 0 0⌧
1,4⌧
3,4⌧
2,3⌧
1,2 図 3: 順列集合{2431,4231,1423} = {τ1,4τ1,2,τ1,4,τ3,4τ2,3} を表すπDD3.2
順列決定グラフ
πDDは互換分解を利用して順列の集合をコンパクト に表すデータ構造である．πDDは節点に互換が書かれ た二分木構造を圧縮したものであり，各節点から伸び る 0-枝，1-枝それぞれがその互換を使う/使わないに対 応する．葉にあたる終端節点は 0 か 1 の 2 通りのラベ ルを持ち，それぞれその終端節点に至るパスに対応す る互換分解が表す順列が集合に含まれない/含まれるこ とを表す． ここで，互換には順序が付けられており，2 つの互換 τi, jとτk,lについて， j > l である，もしくは j = l かつ i < kである場合，τi, jの方がτk,lよりも上位の節点に現 れる．これは互換分解の順序を反映している． 二分木の圧縮には以下の 2 つのルールが用いられる． • 共有: 2 つの節点が同じ互換を持ち，0-枝，1-枝が 指す部分πDD同士がそれぞれ同じであれば，そ の 2 つの節点を共有する． • 削除: 1-枝が直接 0-終端節点を指すような節点を 削除する． 圧縮ルールを図示したものが図 2 である．この二分木 の圧縮ルールは，ZDD [2] という組合せ集合を表すデー タ構造で用いられるものと同様である．順列集合を表 現するπDDの一例を図 3 に示す．πDDは順列集合の単なる圧縮表現ではなく，様々な 絞り込み演算や集合演算を有している．例えば，2 つの πDDが表す集合間の和集合，共通集合，差集合，直積 などの様々な二項集合演算を圧縮した状態のまま適用で きる．ここで順列集合 P, Q 間の直積 P×Q は，P,Q それ ぞれに含まれる順列の積からなる集合であり，P×Q = {ppp(qqq) | ppp ∈ P,qqq ∈ Q} と定義される．これらの演算の計 算時間はπDDのサイズ (節点数) に依存し，表現する 集合の要素数とは直接関係しないため，πDDが表す順 列集合の要素数が多くとも，πDDとして小さく圧縮さ れていれば高速な計算が可能となる.
4
同値類分割アルゴリズム
本節にて本研究の提案アルゴリズムを説明する．そ の前に，順列集合の同値類分割をπDDを利用して行う 既存研究があるため，それを紹介する．提案手法はこ の既存手法とは全く異なる観点から設計されたアルゴ リズムであるが，問題点や特徴の差異を明らかにして 提案手法と比較するために，少し詳しく説明する．4.1
既存手法
YamadaらによるπDDを利用した既存手法 [6] は，置 換群の共役同値類への分割を行う手法 [5] をサイクル タイプ同値類の分割に応用したものである． 群 G において a, b∈ G が共役同値とは，a = gbg−1 と書ける g∈ G が存在することをいう．この同値関係 による同値類が共役同値類である．また，対称群 Snに 関しては，サイクルタイプ同値類と共役同値類は一致 することが知られている．つまり，目的の順列集合に 対するサイクルタイプ同値類分割は，Snの各々の共役 同値類との共通集合を求めることで得られる．よって， まず Snの共役同値類それぞれを表す複数のπDDを求 めた後，それぞれ目的の順列集合を表すπDDとの共通 集合演算を行うことで，サイクルタイプ同値類分割が 得られる． 置換群 G に対する共役同値類分割を求める既存手法 は，下記の手順をとる． 1. P ← ∅ とする 2. Gが空集合ならP を出力し終了する．そうでな いなら x∈ G を 1 つとり，X = {x} とする． 3. Xが変化しなくなるまで X← X ∪∪g∈G∪x∈Xgxg−1 を計算する． 4. P ← P ∪ {X},G ← G \ X として 2. に戻る． 上記の手法は素朴なアルゴリズムであるが，既存手 法では以下の 2 つの工夫により高速化を図る． • R,X,G をπDDで表すことで，アルゴリズム中の 和集合演算，共通集合演算，差集合演算をπDD サイズに比例した時間で行う．さらに，3. の順列 の積を計算する箇所に直積演算× を用いること で，∪g∈G{g} × X × {g−1} と書き換えることがで き，積をまとめて計算できる． • 共役同値関係を定義する際，a = gbg−1と書ける g∈ G の存在が必要であったが，これは G の生 成元 A について g∈ A としてもよいことが示さ れている．よって，3. の g をすべて試す部分は ∪ g∈A{g}×X ×{g−1} と書き換えられる．Snの生 成元としては例えば n−1 個の隣接互換τi,i+1(1≤ i < n)の集合などがあるため，G = Snの場合，試 す g の個数を n! から n−1 に減らすことができる． この手法によるサイクルタイプ同値類分割の問題点 としては， • サイクルタイプ同値類を求めるためには，どのよ うな順列集合 G が入力された場合でも，Snに対 する共役同値類分割を計算することが必要とな る．入力された集合サイズに応じて計算が速くな ることはあまり期待できない． • X が変化しなくなるまでのステップ数や計算途中 でのπDDの大きさの見積もりが理論的に難しい． また，計算途中のπDDは出力には使われないこ とがあり，計算時間やメモリを無駄に消費してし まう可能性がある． などが挙げられる．4.2
提案手法
提案手法では，目的のπDD集合をボトムアップに構 築することで既存手法の問題点の解決を図る．入力の πDDを利用した構築を行うので，提案のアルゴリズム は下記のような特徴を持つ． • Snに関する計算を必要とせず，入力となる順列 集合 G に対応するπDDを基にして計算を行うた め，πDDで効率的に圧縮されるような集合に対 して高速に動作することが期待できる． • 必要な部分に絞って計算を行うため，冗長なπDD の生成を抑えられる． 提案手法の具体的な説明に移る．提案手法では入力さ れた順列集合を表すπDDを辿りながら，目的のπDD をボトムアップに構築していく．このとき，πDDの扱 う互換とサイクル分解に関する性質を利用する．6 5 4 1 2 3 6 5 4 1 2 3 6 5 4 1 2 3 τ2,3 τ1,3 図 4: 互換の適用によるサイクルの結合と分離 まず，ある順列πππに互換τi, jを適用するとき，πππの サイクル分解を考える．すると，i, j が同じサイクルに 含まれている場合，互換τi, jはそのサイクルを分離し， i, jが違うサイクルに含まれている場合，互換τi, jはそ のサイクルを結合する．この様子を図 4 に示す． ここでπDDを考える．τi, jが書かれたある節点の 1-枝が指す部分πDDを P とすると，これは P の順列に 対して，互換τi, jを適用する，と解釈できる．このと き，3.2 節の互換の順序付けより，πDDではτi, jの節点 以下には j≤ l を満たすτk,lが存在しないことに注意す ると，P に含まれる順列πππはπj= jを満たしているた め，πππのサイクル分解において j は必ず大きさ 1 のサ イクルに含まれる．よって，P に互換τi, jを適用するこ とは，i を含むサイクルに j を結合することに対応する． 各サイクルには要素の追加しか起こらないので，同 じ要素からなるサイクル同士であれば，たとえサイク ル内での要素の順番が違っていても，同じ互換列によっ て追加される要素は変わらない．よって，違うサイク ルから構成される 2 つの順列であっても，各サイクル を構成する要素の集合が同じであれば，同様に互換を 適用していった結果のサイクルタイプは同じになるの で，まとめて扱ってよい．したがって，部分πDDに対 し，各サイクルに含まれる要素の集合からなる族が一 致する順列ごとに分割したπDDの族を構成できれば， それぞれにτi, jを適用してできるπDDは，i が含まれ る集合に j を加えた集合族に対するπDDと考えられる ため，τi, jを根の節点とするπDDに対する分割も再帰 的に求められる．これを Algorithm 1 に示す． ここで，各々のπDDに対応するサイクル要素の集合 の族がわかっているので，各サイクル要素の集合のサ イズから，対応するサイクルタイプが計算できる．よっ て，Algorithm 1 で求めた各πDDが表す集合族ごとに サイクルタイプを計算し，同じサイクルタイプを持つ πDDをすべて和集合演算でまとめてやれば，各サイク ルタイプに対応するπDDが得られる．このアルゴリズ Algorithm 1サイクル内の要素が同じ順列集合からな るπDDの族を求めるアルゴリズム 入力:πDD 出力: 各サイクルに含まれる要素が同じ順列の集合 からなる族を表すπDDの族 SetPartition(πDD P): Pの根の節点をτi, jとする L← P の 0-枝が指す部分πDD L ← SetPartition(L) R← P の 1-枝が指す部分πDD R ← SetPartition(R) for S ∈ {1,..., j − 1} の集合分割からなる族 do SL← S ∪ {{ j}} XSL← XSL∪ LS iがS の k 番目の集合に含まれるとする SR← S の k 番目の集合に j を追加した集合族 XSR← XSR∪τi, jの 1-枝の先がRS を指すπDD (0-枝は 0-終端節点を指す) end for return X Algorithm 2サイクルタイプ同値類分割を表すπDDの 族を求めるアルゴリズム 入力: 順列集合を表すπDD 出力: 各πDDが 1 つのサイクルタイプ同値類に対応 するようなπDDの族 CyclePartition(πDD P): P ← SetPartition(P) for S ∈ {1,...,n} の集合分割からなる族 do ccc← i 番目の要素が S に含まれるサイズが i の集 合の個数に対応するベクトル Xccc← Xccc∪ PS end for return X ムを Algorithm 2 に示す． ここで，各サイクルに含まれる要素の集合の族は， 集合{1,...,n} の分割の 1 つと考えられるので，Algo-rithm 1の各再帰ステップでの計算時間は，{1,..., j} の 集合分割の個数で抑えられる．{1,..., j} の集合分割の 個数はベル数 Bjとして知られているため，Algorithm 1 の時間計算量は入力πDDの節点を N として，O(NBn) で抑えられる．実際は，各節点ごとに j が異なったり， 入力の順列集合に現れない集合分割も存在しうるため， この見積もりよりも高速に動作することが期待できる． 一方 Algorithm 2 では最悪 Bn回の和集合演算が行われ るが，1 回あたりのπDDの和集合演算の時間を見積も ることが困難なため，計算時間の具体的な上界を求め ることは困難であるものと思われる．
表 1: Snに対するサイクルタイプ同値類分割アルゴリズムの実行結果 既存手法 提案手法 提案手法/既存手法 n 実行時間 (sec) 使用メモリ (MB) 実行時間 (sec) 使用メモリ (MB) 実行時間比 使用メモリ比 8 0.31 35.8 0.02 34.4 0.065 0.961 9 2.70 269.8 0.12 56.0 0.044 0.208 10 21.50 1182.3 1.25 280.7 0.058 0.237 11 169.88 9047.8 10.21 2053.9 0.060 0.227 12 1479.63 64558.5 78.56 15035.3 0.053 0.233
5
実験
5.1
実験結果
提案アルゴリズムの実用上の性能を評価するために， 計算機実験を行った．5.2
実験設定
アルゴリズムの性能に集中した評価を行うため，サイ クルタイプ同値類分割を求めたい順列集合に対応する πDDをあらかじめ用意し，そのπDDを入力として用 いた．順列集合としては，順列の長さ n を 8 から 12 ま でに対する Snを用いた．実験には Intel Core i7-3930K 3.20GHz，メモリ 64GB の計算機を使用した． 実験結果を表 1 に示す．提案手法の方が計算時間で 約 20 倍，使用メモリで約 5 倍効率がよいことがわかる． 計算におけるボトルネックは時間よりもメモリであり， 提案手法でも n = 13 のケースではメモリが足りず，計 算できなかった．前節にもあった通り，既存手法は Sn に対する同値類分割を計算した後，入力となる順列集 合と更に共通集合を計算する必要があるため，どのよ うな順列集合が入力であっても，それぞれの n に対し て必ずこの表 1 にある計算時間，メモリが最低限必要 になる．一方，提案手法の利点として，Sn以外の入力 に対しても直接計算が可能であるため，より少ないメ モリで計算できる可能性がある．6
結論
本研究では与えられた順列集合に対し，そのサイク ルタイプ同値類を圧縮表現したπDDを生成するアルゴ リズムを提案した．計算機実験の結果，提案手法は既 存のπDD生成アルゴリズムに比べて高速・省メモリで 動作することが確認できた． 今後の課題としては，ボトルネックとなっているメモ リ効率の改善を図ることや，既存手法が行っている共 役同値類分割の計算にも提案手法のアイデアを応用し て改善ができないか考えることなどが挙げられる．ま た，求めたサイクルタイプ同値類分解を応用的な問題 の解決に利用することも検討していきたい．謝辞
本研究は JSPS 科研費 15J01665 および 15H05711 の 助成を受けたものです．参考文献
[1] Yuma Inoue and Shin-ichi Minato. An efficient method for indexing all topological orders of a di-rected graph. Proc. of 25th International Sympo-sium on Algorithms and Computation, pages 103–114,
2014.
[2] Shin-ichi Minato. Zero-suppressed bdds for set ma-nipulation in combinatorial problems. Proc. of 30th
ACM/IEEE Design Automation Conf.(Dac-93), pages
272–277, 1993.
[3] Shin-ichi Minato. πDDs: A new decision diagram for efficient problem solving in permutation space.
Proc. of 14th International Conference on Theory and Applications of Satisfiability Testing, pages 90–104,
2011.
[4] S. Gill Williamson. Polya Counting Theory :
Combi-natorics for Computer Science. CreateSpace
Indepen-dent Publishing Platform, 2012.
[5] Norihiro Yamada and Shin-ichi Minato. AπDD-based method for generating conjugacy classes of permuta-tion groups. TCS technical report TCS-TR-A-12-56,
Division of Computer Science, Hokkaido University,
2012. [6] 山田 倫大，湊 真一. DS-1-13πDDの conjugacy class 計算への適用とその性能評価 (DS-1.COMP 学生シン ポジウム, シンポジウムセッション). 電子情報通信 学会総合大会講演論文集, 2012(1):”S–25”–”S–26”, March 2012.
