« Cが最速なんてもう言わない | Main | 今日の日記 »

2007.11.05

Iteratorで順列を作る

Higher-order Perlから

Chap4はiteratorの話。一番身近なiteratorはファイルハンドル、という説明は分かりやすい。

タイトルの通り、Iteratorを使って順列を作る話。('A' 'B' 'C')のリストからこんな出力が欲しい。
[A B C]
[A C B]
[B A C]
[B C A]
[C A B]
[C B A]

普通に再帰を使って順列を作ると、CPUとメモリを大きく消費するし、順列に対して一つずつ処理するのがやりにくい。(ファイルハンドルでも、ファイルを全部読み込みたいときと、1行ずつ or 一文字ずつ処理したいときあるよね)

そこでIteratorを使う。
面白いのが、まずこんな感じのカウンターを作ります。(名前ありそうだけどね)

0000
0010
0100
0110
0200
0210
1000
1010
1100
1110
1200
1210
2000
2010
:
2210
3000
3010

3200
3210

最下位の桁は0固定として、その次から下位から順に、2進、3進、4進のカウンターになっています。4桁だとちょうど24個で、順列の数になっています。0000から始まって、3210が最大です。3桁だと、000から210までなので、これも3個の順列で6個の値を取ります。

戦略としては、iteratorを使ってこのカウンターを順次インクリメントする→カウンターの値から対応するリストを取り出す、になります。順列を一つずつ作る部分と、順列からリストを作る部分が分離しているのが美しい。

目的のリストのつくりかたを簡単に説明します。カウンターの最上位に対応する要素を抜き出します、抜き出されて要素が一つ減ったリストと、カウンターの最上位を取り除いた物で同じように処理します。簡単な再帰なのですが、文章だけではわかりにくいと思います。

もとのリストが、(A B C D)カウンターの値が2010の時、カウンターの最上位が2なので、Cを取り出します。

元のリスト カウンター 新しいリスト
(A B C D) 2010     ()
(A B D)   010    (C)    ← Cを抜き出し、カウンターの最上位を取り除く。

次は、カウンターの最上位が0なので、(A B D)の0番目にあたるAを取り除きます。

(B D)    10   (C A)    ← Aを抜き出し、カウンターの最上位を取り除く。

次は、カウンターの最上位が1なので、(B D)の1番目にあたるDを取り除きます。

(B)     0  (C A D)    ← Dを抜き出し、カウンターの最上位を取り除く。

最後、カウンターの最上位が0なので、(B)の0番目にあたるBを取り除きます。

()         (C A D B)    ← Bを抜き出し、カウンターの最上位を取り除く。

これで、(A B C D)と2010から、(C A D B)が取り出せます。

使い方はこんな感じです。
my $it = permute('A' .. 'D'); #iteratorを返す

while (my @p = $it->()) { # iteratorが空のリストを返すまで順次インクリメント
 print "@p\n";
}

package Iterator_Utils;が上手く使えず、自力で書いたのは秘密。

|

« Cが最速なんてもう言わない | Main | 今日の日記 »

Comments

Post a comment



(Not displayed with comment.)




TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/18154/16986882

Listed below are links to weblogs that reference Iteratorで順列を作る:

« Cが最速なんてもう言わない | Main | 今日の日記 »