なつたん

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;が上手く使えず、自力で書いたのは秘密。