Algorithm::Permute - Handy and fast permutation with object oriented interface

Location : Home > Languages > Perl > Package
Title : Algorithm::Permute

　Algorithm::Permute - 高速に順列を生成

use Algorithm::Permute;

my $p = new Algorithm::Permute(['a'..'d']);
while (@res = $p->next) {
   print join(", ", @res), "\n";
}

my @array = (1..9);
Algorithm::Permute::permute { print "@array\n" } @array;

説明

　このハンディなモジュールは Perl で簡単で高速に順列を生成する。しかしアルゴリズムは地上で最速と言うわけではない。現在では n 個から n 個抽出する順列のみを提供している。
　エクスポートする関数はない。本バージョンは過去のバージョンに対する互換性がない。古いインタフェースはもはやサポートされない。

メソッド

new [@list]: 　所与の項目の permutor オブジェクトを返す。
next: 　次の順列の項目のリストを返す。結果の順列の順序は Algorithm::Permute の過去のバージョンと同じである。
peek: 　next() で返されるべき項目のリストを返すが、シーケンスは進まない。いくつかの望まない順列をスキップするには有用である。
reset: 　計数を最初に戻す。全集合を生成するか否かと言うときには有用である。有用な返り値はない。

コールバックスタイルインタフェース

　version 0.03 から開始。デフォルトではエクスポートされない、コールバックスタイルインタフェースを提供する関数である。

permute BLOCK ARRAY

　コードのブロックが渡されればそれぞれの順列を計算する。配列は置き換えられ、 permute が返す前に再度変更される。コールバックの実行中は配列は読み込みのみ可能で、長さを変更しようとするとエラーが出る。（要素を変更することはできるが、その結果はユーザを混乱させがちなので将来のバージョンでは変更するかもしれない。）
　リストではなく、配列を渡さなければならない。特に複雑な配列でない限りは最初に配列をコピーするとよい。例えば、

my @array = (1..9);
permute { print "@array\n" } @array;

　コードは内部ではサブルーチンではなく、ブロックのように動く。これは return を使うことも goto を使ってジャンプすることもできないことを意味する。また caller はコールバック内部からはユーザに何も有用なことを教えない。これは速度の代償である。
　順列が生成される順序は保証されないので信頼しないこと。
　この関数の低レベルのハックは順列を速く計算する最良の方法かもしれない。

比較

　順列を実装している Perl のルーチンやモジュールを集めてベンチマークを行った。全ての結果は以下の通り。
　８つのスカラの順列を計算させた結果である。

Abigail's                     :  9 wallclock secs ( 8.07 usr + 0.30 sys =  8.37 CPU)
Algorithm::Permute            :  5 wallclock secs ( 5.72 usr + 0.00 sys =  5.72 CPU)
Algorithm::Permute qw(permute):  2 wallclock secs ( 1.65 usr + 0.00 sys =  1.65 CPU)
List::Permutor                : 27 wallclock secs (26.73 usr + 0.01 sys = 26.74 CPU)
MJD's                         : 32 wallclock secs (32.55 usr + 0.02 sys = 32.57 CPU)
perlfaq4                      : 36 wallclock secs (35.27 usr + 0.02 sys = 35.29 CPU)

　次は９つのスカラに対する結果である。（ただし Abigail のルーチンはコメントアウトした。これは全ての結果をメモリに格納するため、マシンのメモリを使い尽くすからである。）

Algorithm::Permute            :  43 wallclock secs ( 42.93 usr + 0.04 sys =  42.97 CPU)
Algorithm::Permute qw(permute):  15 wallclock secs ( 14.82 usr + 0.00 sys =  14.82 CPU)
List::Permutor                : 227 wallclock secs (226.46 usr + 0.22 sys = 226.68 CPU)
MJD's                         : 307 wallclock secs (306.69 usr + 0.43 sys = 307.12 CPU)
erlfaq4                       : 272 wallclock secs (271.93 usr + 0.33 sys = 272.26 CPU)

　ベンチマーク用のスクリプトは bench ディレクトリにある。速度が全てではないということがわかった。個のモジュールが大嫌いな場合には他の選択すとしてこれらの URL リストをつけておく。

Mark Jason Dominus のテクニックについては Perl Cookbook の第4章で議論されている。これはオライリーで手に入る。：ftp://ftp.oreilly.com/published/oreilly/perl/cookbook
Abigail のサイト：http://www.foad.org/~abigail/Perl
List::Permutor: http://www.cpan.org/modules/by-module/List
たいてい Lisp ハッカーに使われる古典的な方法なら perldoc perlfaq4

履歴

September 5, 2001 - version 0.03. 高速のコールバックスタイルのインタフェースが追加された。
September 2, 2000 - version 0.02. 主要なインタフェースが変更。List::Permutor に似たオブジェクト指向インタフェースを使用。効率的なメモリ利用となっている。内部調整により速度を改善した。リスト要素はもはやスワップされない。インデクスだけがスワップされる。
October 3, 1999 - アルファ版リリース。 version 0.01

著者

　Edwin Pratomo, <edpratomo@cpan.org>.

　オブジェクト指向インタフェースは Tom Phoenix の List::Permutor からとった。 Robin Houston <robin@kitsite.com> はコールバックスタイルのインタフェースを作成した。

謝辞

　Yustina Sri Suharini - 順列の問題を私に投げかけてくれた。

参考資料

Data Structures, Algorithms, and Program Style Using C - Korsh and Garrett
Algorithms from P to NP, Vol. I - Moret and Shapiro

Updated : 2007/07/26