Title Author(s) Citation Issue Date Type 順列の生成法 山崎, 秀記 情報処理, 24(4): 378-381 1983-04-15 Journal Article Text Version publisher URL http://hdl.handle.net/10086/16410 Right Hitotsubashi University Repository Vol .24 No.4 情 報 処 A 理 7.順 列 の 生 成 法T 山 崎 秀 記IT 本稿では 1. ま えn個の要素からなる か き 生成す る手続 きを紹介する. こ順列すべてを効率 よ く B Z ) 1 ようで,1 れ 自身興味ある問題の 81 2句 こはすでに,すべて 序で生成する手続 きが発表 されて の順列を辞書式J r B のが単純で,解 くことはそ う易 P T .1 9 8 3 圭 にしらみつぶしの探査を 図2 例えば 3次の魔法陣 ( 避 けるのにも役立つ. 例,図 1 ) いる1 ) . 問題そのも き, 1か ら 9までの数か らなる順列をすべて求め. ると ; 味を引いたのだろう.またその しくないので先人の興 の良 PI P2 -P9をす るかどうか調べる, としよう.,図2が 魔法陣にな べて生成 し,それぞれについて 意味でプログラミング さて実際の場面であらゆる場 い練習問題でもある. ( 順列を 9桁の数 とみて小 さい この とき,辞書式塀序 べてみたいときに, n次の順列合をしらみつぶしに調 法をとれば, 順列の生成が大幅 順で順 列 を生成する方 きが ほし くなることがある.しをすべて生成す る手続 に省略で きる.まS, 123456789 というJ r A列か ら調べる えば,それは nが大 きいときはさ かし結論を言 って しま n. n次 けた方がよい の順列は全部で n!個あ り,どう工夫しても 省略で きる. つまりこの問題につい t .個の順列の生成が 8 0 0 36 2万 8 あらゆる順序で入れ換わった後 9 1万 6 1 2! - 4 39 8 0 0 うな順列生成法が 1 引-6 2億 79 0 0万 1 6 0 0 その a営業所, B本社 とその も営てみよう.A本社と 2 くらい べての順列が生成で き るのはたかだか n-1 社の 6カ所を今 日中に廻 りたい 業所,他 こC社,D 際の応用問題では,J I A列生成にまで である. しかも実 ずその本社に寄るとして 最 も .営業所へ着 く前に必 された順列の処理にかか る手間かか る手間より,生成 る. この場合,Aと a,Bとも 速 く訪 れ る順序を求め のが普通であ る.だ とすればどの生成方法を用いる の方がはるかに大 きい 順序になっていない順列は調べの相対的順序が,この って この問題に適 しているJ J j g列 る必要がない.したが か て 1 生成法は,各 , 2 ,-, iの相 対 的 位 置が不変のまま , iについ き,すべての順列をいかに効率 みつぶしに調べたいと があらゆる位置に現れ,その後 問題に精力をそそぐよりも, どよ く生成す るかという わ る, と を生成しな くてもすむか, しらうした らすべての順列 避けるか,に精力を ては PL ' 1 -PAが 初めて Plが換わるよ こんどは次のような問題を考え 適 しているといえる. 上の表か らわかるように,す 億2 7 0 2万 0 8 0 0 は余 結局,ある問題についてしら り差がない. : 3 わけだが,12 ら P9をどう入れ替えても魔法 6 ≠1 5なので P4か って,J r R列 123987654まで陣にならない.したが 6 !の手 間がかか 1 0! る. 1 1! - ･ ･ ･となる順列は Pl +P2 +P3 - i +1 ,-I , 7 2 で初めて iの位置が変 最 も速い順列生成の方法 いった手続 きである. とい みつぶしの探査をどう 要ではないにしても,いろいろなJ うのは実用上さして重 それでも,どうして そそぐべ もすべて きであ' 8一 ることは意味があるし,それ 白 があるときは本稿が参考になるの順列を生成する必要 r R列生成の手法を知 る.本稿では 2章で順列中の 2身興味を引 く問題であ 次と新しい順列を生成 してい く方 要素の交換によって次 だろう .またそれ以上 IAl g o r i t hmsf orGe ne r at i ngPe r mut a t i o nsby Hl SAKI( Tokyol ns t l t ut eOfTe c hnol o gyDe pa r t m d e e n k t iYAMAI ma t i o n ofl nf o r ･ ‡ ニ ー : - 生 法を, 3章では巡回 置換による方法を, 4章では辞書式順序の順成 †I東京工業大学理学部情報科学科 Sc i e n c e ) . 3 7 8 γol .24 No.4 3 7 9 順列の生成法 ここで以下の章の記述を簡単にするためにいくつか を書けるが, ここでは他の手続 きとの比較上,再帰呼 F B列は大 きさ nの配列 Pで の記法を定めよう.n次のJ i ]で P[ i ]と び 出 しを用 い な いで書 く. 配列 C[ 表わす.要素は 1か ら nまで とし最初は常に P[1]- P[1‥i -1] のどれかとの交換の回数 ( 正しくは 回数 1 , -,P[n]-n である. ( 要素が 1か らnまでの数で i ]<iなる最小の i( ≧2)を見つ け +1 )を表わす.cl あるという仮定は手続 きT4以外では本質的でない. ) て,P[ i ]での交換を行い,このとき C[ 1"i-1] をそ 配列 P の一部を参照したい こ とが よ くあ る.そこ れぞれ 1に置 き直せば目的の手続 きがえられ る. ],-･ ,P[j]( 1≦i <j≦n)を P[ i. . j]で表わ で P[i pr oc e dur eTl; す.したが って P[1‥n] は配列 P 全体を表わす. 2章では P[i ] と Pl j]の交換が基本操作となる. これを P[ i -j] と書 く. 例えば P[1. . 5]-43125 pr OC e S S; f ori : -2 t on docl i ]= =lod･ ,i: -2; r e pe ati fcl i ]<i に対し,P[ 2←4] を実行した結果は P[1. . 5]-421 一● 35である.巡回置換は P[i‥j]で表 わ す. これは t he n P[ i -i nde x];pr oc e s s; P[ i ]に P[ i +1] を,P[ i +1]に P[ i +2]を,- e l s ec[i ]･ -1;i : -i +1f i P[ j-1 ] に P[j]を,そして,P[j]には P[ i ]を 代入することを意味す る.例えば, P[1. . 5]-43125 ◆ ･ -に P[ 2‥4]を実行した結果は P[1. . 5]-41235で ● 一ある,P[i‥j]を逆順に並べかえ る操作は P[ i. . j] : +∴ し で表わす.P[1. . 5]-43125のとき P[ 2‥5]を実行 , すると,P[1‥5]-45213 となる. 以下の章で与える手続 きでは,順 列 生成 手 続 きを " 主プログラム"と考えて, 順 列 を生成するたびにそ cl i ]= -cl i ]+1;i : -2 unt i li >N. さて P[ i ]の C[ i ] 回目の交換の相手の指標 i nde x を求める問題が残 っている.表として覚えてお くこと もで きるが,We l lのアル ゴリズム8 )では i nde x･ -i f( iは偶数)t he n i-C[ i ]e l s eill , He a pのアルゴリズム2)では i nde x: -i f( iは偶数)t he n cli ]e l f l e1 , である.He a pのアルゴリズムの計 算 例 を示 そ う. の順列を処理する手続 き pr oc e s sを 呼 ぶ よ うにして ( n-4)1 23 4 .21 3 4 ,畠i 24 ,1 3 24 ,畠51 4 ,3 21 4 ,4 21 3 , ある. 24 1 3 ,1 4 2 3 ,41 2 3 ,21 4 3 ,1 24 3 ,1 34 2 ,31 4 2 ,41 3 2 , なお, この解説は Se dge wi c k6 )を主 に参考にして 1 4 3 2,34 1 2 ,4 31 2,4 3 21 .34 21 ,24 31 ,4 2 31 ,3 24 1 , 書いた. これは順列生成の秀れた概説であ り,詳しい 23 4 1 .( ･ 印は次の順列を生成す るための交換の場所を 参考文献がついている. より詳しく知 りたい読者は, 表わす. ) ､ これを手掛 りにすることをお勧めす る. -1 ]の順列をすべ これ らの手続 きの特徴は,P[1‥i て生成してか らは じめて P[ i ]を動かす こ とである. 2.交換 に よ る方 法 ある順列か ら新しい順列をえる手近な方法は, 順列 の2個の要素を交換することだろう. この童では交換 2 . 2 繰 り返 し的方法 1 ,･ ･ ･ ,n-1 の各J r B列に対して, その要素の問 ( 両端 を含めて nカ所ある)に nを順に入れてい くと 1 ,-, によって, n次の順列すべてを次刺 こ生成す る手続 き n の順列がすべてえ られる.この考 え方 に従 って, 嫁紹介す る. ot t e r 7) は独立に 1 9 6 2年に,隣接要 Johns on3) と Tr 2 . 1 再帰的方法 -1 回で n次のJ r B列をすべて生成す る手 素の交換 n! P[ 1‥n] の 順 列 を す べ て 生 成 す るに は, まず 続 きを示 した. P[ 1‥n-1 ]の順列をすべ て 生 成 し,次に P[ n] と i ]で 要 素 iが 何 回 動いたかを覚えておけ 配列 cl P[ 1‥n-1 ]のどれかひとつ とを交換 し, 再び P[ 1. . ]<iなる最大の iが次に移動す る要素である. ば,cli n-1 ]のすべての) J R列を生成す る, ということを くり したがって手続 きの枠組みは次のようになる. 返せばよい.P[n] に 1 ,･ -,nがすべて 1度ずつ現れ pr OCeS S; るようにすれば,p[ 1‥n] のすべての 順 列 を生成で f o ri = -2 t o n docl i ]=lod;i : -n せる.具体的に,P[n] をどれ と交換すればよいか と r e pe ati fcli ]<i いう問題はさておいて ( 後で見 るよ うに何通 りも解が ある) , この考えに沿 った手 続 きを書いてみよう.考 え方が再帰的なので,再帰呼び出しを用いても手続 き t he m P[ i nde x←i nde x+1 ];pr oc e s s; cl i ]: -cl i ]+1;i ･ -n; e l s ec[ i ]L -1;i ユ ニi -1f i 3 8 0 情 報 処 Apr .1 9 8 3 理 t L nt i li <2. 二 + P [ 1 ‥i ]を用いる.巡 l 司置 換 を用いる方法にも再帰 ここで要素 iは P[ i nde x]か P[ i nde x+1 ] に入 的方法と繰 り返し的方法 とがあるが ここでは繰 り返し っている.i nde xの求め方を調べるために,どんな列 的方法を述べよう. を生成したいのか眺めてみよう. pr oc e dur eT3; 1 2 34 ,1 24 3 ,1 毎 41 23 ( 4が左へ) 41 3 2,1 4 3 2 ,1 34 2,1 3 2 4 , ( 次に 3が 1つ左へ動 き, 4は今度は右へ移動す る) pr OC e S S; f ori = -2t ondocl i ] : -1od;i : -n; +i . i ]; r e pe atPl1. 31 24 ,31 4 2,3 4 1 2,4 31 2 i fc l i ]<i , 2 , 3の中では左端に来たので, 2が左へ. ) ( 3も 1 4 3 21 ,34 21 ,3 24 1 ,3 21 4 t he nc [ i ]; -C[ i ]+1; i = -n;pr oc e s s e l s ec [ i ] : -1;i : -z L 1f i unt i lZ <2 ( 3が今度は右へ) 231 4 ,23 4 1 .24 31 ,4 23 1 2章の手続 きとは異な り,巡回置換を施す位置を求 4 21 3 ,24 1 3 ,21 4 3 ,21 3 4 ( 4 , 3 , 2すべて端に来ている. 1を 動 か す番になった ので終 り. ) 隣接要素の交換だけですますために,各要素が左へ める手間は要 らない.しかし巡回置換 自身の手間がか ● -かることと ( P[ 1. i ]は iに比例す る手間がかかる) , ⊂ = : ≡ P[ 1. . i ]を ( i -1 )回施したあと, もう一度 P[ 1‥i ] 論理型の配列 d[ i ]で,左なら真,右なら偽,と覚え を施 して順列を元の状態 に戻 して い る ( 手続 き中の ◆ -･ P. [ 1 -i]の位置に注意) ことか ら, このアル ゴリズム は決して効率のよいものではない.にもかかわ らずこ [ i ]回目の移動 ( 交 てお く. さて問題は, 要素 iは C こで紹介した理 由は次のような単純な手続 きがえられ 換)の ときどの位置にいるか,である. 1から iまで るか らである. 動いた り右へ動いた りすることに注意しよう. これを の中では,左へ動 いて いるときは i +1-cl i ]番 目に l i ]番目に居 る.全体 いて,右へ動いているときは c の中では,i +1か らnまでの中でその とき左 端 に来 こ =配列 c l 7 ]の役 目は,P[ 1‥i ]を何回行 ったかを覚え ■ -てお くことである.P[ 1‥i ]を実行するのは c l i ]<i し,次の手続 きがえられ る. なる最大の数のときである. このときまでに手続 きは = : P[ 1. . n] を n回実行 して P[ n]-n,P[ 1, . n-1 ]を = =n-1 ]-n-1 , ･ ･ ･ , P[ 1日i +1 ]を n-1回実行 して P[ pr oc e dur eT2;( J ohns on3 )Tr ot t e r 7) ) i +1回実行して, P[ i +] . ]-i +1 , である. しか し ている要素 ( 即ち d[ j]が真から偽に変 った j)の数 だけ右へず らさなければならない. このずれを∬で現 pr OC e S S; f o ri : -2t ondoc l i ] : -1;dl z L ] : -t r ueod;i : -n; i ]<i re pe ati fcl t l l e r Li fdl i ]t he ni nde x: -i -C[ i ]+X e l s ei nde x･ -C [ i ]+E丘; P[ i nde x-i nde x+] ];pr o c e s s; C[ i ] ･ -C [ i ]+1;i = -n;a: -0 e l s ei fd[ i ]t he na: =x+1f i; dl i ] ･ =notdl i ]; cl i ] ･ -1;i ･ -i -1f i unt i li <2 . この方法の特徴は, 1から i -1 までの相対的順序 が不変のまま,iか ら n までがあらゆる位 置 を動 く ことである. 3.巡 回置換 によ る方 法 1日i ] の巡回置換 この章では基 本 演算 として P[ こ = P[ 1‥i ]はまだ i回実行されていないので P[ i ]<iで ある. 即ちこの手続 きは P[ i ]<iなる最大の iに対 ■ ･ して P[ 1. . i ]を実行す る.配列 C [ i ]は必要ない. proc e dur eT4;( La ngdon4)) pr OC e S S; l ; =n; こ = ]; r e pe atPllHi i fPl 1. . i ]<it he ni : =n;pr oc e s s e l B ei ; =i -1f i unt i li <2. この手続 きは見かけ上最 も単純なものだろう. 4 .辞書 式順 序 の生成 この章ではすべての順列を辞書式順序で生成する手 続 きを示す.再 帰 的 に考えてみよう.P[ 1‥n]のす べてのJ J R列を辞書式順序で生成するには,まず P[ 2‥ r R序で生成す る. その結果 P[ 2‥n]は n]を辞書式J γo l .2 4 No.4 3 81 順列の生成法 大きい方か ら逆に並んでいるか ら,P[ 1 ]と Pl n]を pr oc e dur eT6; 交換し,P[ 2. . n] を逆に並べかえる.再び P[ 2. . n] J: -nll; の順列全部を辞書式 順 序で 生 成 す ると こん ど は, whi l ej<lorPlj]>Plj+1]do j: =j-1o d; P【 1 ]-2,Pln-1 ]-3,Pln]-1となるか ら P[ 1 ]と i fj>lt he r L P[ n-1 ]を交換し Pl 2. . n] を逆 に並べかえる. こ k: -n; 1 ]に 1 , 2,-,n が この 順で現れ, うしていけば P[ whi l eP[j]>P[k]dokま -k-1od; : ≡ == P[j-k];P[j+1‥n] Pl 1‥n]の順 列 を辞書式J I B序ですべて生成で きる. 基本方針はこれでよいのだが,次の手続 きでは,配列 丘 の添字の計算と簡単にす るために,順列を配列 P[ 1. . この手続 きを最初か ら順列全体が逆順になるまで繰 n ]ではなく,P[1‥n]-Q[n‥1 ]なる配列 Q[1‥n] り返せばすべての順列が生成で きる.それが Fi s c he r ･ を用いて表わす. Kr a us e l )の方法である. p r o c e dur eT5;( Or d･ Smi t h5) ) p r O C e S S; : -2t o n_ doc[ i ] = -1od;i = -2 f o ri r e pe ati f cli ]<i 一･ ･ ･ ･ ･ 一 一 一 一 一 一 ◆ t l l e n Q[ i ‥cl i ] ];Ql1. . i -1 ]; pr OC e S S; cl i ]･ -cl i ]+1;i : -2 e l s ec[i ]･ -1;i l -i +1f i unt i li >n. Q[ n. . 1 ]-( 1 , 2,･ ･ ･ ,n)で始めれば, Q[ n-1 ]に1 , 2 , -, nのすべてのJ l R列が辞書式J ) R序で現れ る.もし もとの配列 P[ 1. . n]で計算したければ, Q[ i -C[ i ]] を P[ n+11' ←n+1-cl i ]] に, - - 一 ･ . ･ . ･ . ･ → P[ n+2-2 ' ‥n] に, 十 ･ ･ . ･ . -◆ Q[ 1. . i -1 ]を 置きかえればよい. 配列 P[1. . n] に戻って議論を進めよう.上の手続 n+1-i -n+1-cl i ] ]が行われ るときの きで命令 P[ ( n+1-i ) の 値 は, Pl j]<P[j+1 ]>P[j+2]>･ ･ ･ ,P [j]の 交 換の相手 P [j] の次に小 さい要素である･ >p[ n] なる j の値に等し く は Plj‥n] 中の このことか らある順列 Pl1. . n] が与えられた とき, それを辞書式順序で次に くる順列に変換す るには次の ようにすればよいことがわか る. 参 考 文 献 1 )Fi s c he r ,L L and Kr a us e ,K. C∴ Le hr buc h de rCombi na t i ons l ehr eund de r Ar i t hme t i k, Dr e s d; n( 1 8 1 2 ) . R･ :Pe r mut a t i onsby i nt e r c ha nge s , 2)He a p,B･ Co mput ,J . ,Vol ･1 8,No.1 ,pp.29 3 1 29 4( 1 9 6 3 ) . 3 )J ol ms on,S. M.:Ge ne r a t i on ofPe r mut a t i ons byadj a c e ntt r a ns pos i t i on,Ma t h.Co mput . ,Vo l . 1 7 ,pp.28 2 28 5( 1 9 6 3 ) . 4)Lo ngdon,G･ G･ ,J r ･:Ana l gor i t hm f orge ne r a t i ng pe r mut a t i ons ,Comm.ACM,Vol .1 0 , No.5 ,pp.29 8 2 9 9( 1 9 6 7 ) . 5 )Or d･ Smi t h,良. ∫ .:Ge ne r at i onofPe r mut a t i ons i nLe xi c o gr a phi cOr de r ,Co mm.ACM,Vol .ll , No.2,p.1 1 7( 1 9 6 8 ) . 6)Se d ge ic w k, A. : Per mut a t i o n Ge ne r a t i on Me t hods ,Co mput ･Sur v" Vo1 .9 ,No,2,pp. 1 3 7 -1 5 5( 1 9 7 7 ) . 有浮 誠訳 :順列生成の手法,bi t ,Vo l .1 0 ,No. 6 ,pp,6 9 9 7( 1 9 7 8) . 7)Tr ot t e r ,H. F.:Pe r m,Co mm.ACM,Vo l .5, No.8,pp.4 3 4 4 3 5( 1 9 6 2) . 8 )We l l s ,M. B∴ Ge ne r a t i onsofPe r mut a t i onsby t r a ns pos i t i on,Ma t h.Co mput "Vol .1 5 ,pp.1 9 2 1 9 5( 1 9 6 1 ) . ( 昭和 5 7年 1 2月 1 日受付)
© Copyright 2024 ExpyDoc
