Title : Algorithm::Combinatorics
|
Location : Home > Languages > Perl > Package Title : Algorithm::Combinatorics |
|
Algorithm::Combinatorics - 組み合わせの効率的生成
use Algorithm::Combinatorics qw(permutations);
my @data = qw(a b c);
# スカラコンテキストなら反復演算子を
my $iter = permutations(\@data);
while (my $p = $iter->next) {
# ...
}
# リストコンテキストならそのまま
my @all_permutations = permutations(\@data);
本ドキュメントは Algorithm::Combinatorics version 0.15 用のものである。
Algorithm::Combinatorics は組み合わせ列の効率的生成を行う。アルゴリズムは文献（参照）を参照した。繰り返し計算は回帰もスタックも使わず、C で書かれている。
対は辞書的順序で生成される。
Algorithm::Combinatorics は以下のサブルーチンを提供する。
permutations(\@data) derangements(\@data) variations(\@data, $k) variations_with_repetition(\@data, $k) tuples(\@data, $k) tuples_with_repetition(\@data, $k) combinations(\@data, $k) combinations_with_repetition(\@data, $k) partitions(\@data[, $k])
これらは全てコンテキスト依存である。
スカラコンテキストでは、サブルーチンは next() メソッドに対応する繰り返し演算子を返す。このオブジェクトを用いれば以下のようにして対の列全体を繰り返すことができる。
my $iter = combinations(\@data, $k);
while (my $c = $iter->next) {
# ...
}
next() メソッドは次の対への配列参照を返す。列が終了した場合は undef を返す。メモリ使用は最小限で、回帰もスタックも利用しない。
リストコンテキストではサブルーチンは全ての対の集合をなめる。この方法は便利だが結果の配列は非常に大きくなる。
my @all_combinations = combinations(\@data, $k);
permutations(\@data)
@data の順列は並び替えられる。例えば @data = (1, 2, 3) の順列は以下の通りである。
(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)
n 個の要素の順列の個数は
n! = 1, if n = 0 n! = n*(n-1)*...*1, if n > 0
derangements(\@data)
@data の完全配列（derangements）はそれ自身の番号の位置に要素がないように並び替えられた配列のことである。固定点のない @data の順列とも言い換えることができる。例えば @data = (1, 2, 3) の完全配列は以下の通り。
(2, 3, 1) (3, 1, 2)
n 個の要素の完全配列の個数は
d(n) = 1, if n = 0 d(n) = n*d(n-1) + (-1)**n, if n > 0
variations(\@data, $k)
@data の長さ $k の variations とは、@data の要素からなる長さが $k の対の全体である。例えば @data = (1, 2, 3) 及び $k = 2 であれば以下のようになる。
(1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2)
これが意味を持つためには $k は @data の長さ以下でなければならない。
また以下のことに注意すること。
permutations(\@data);
は以下の式と等価である。
variations(\@data, scalar @data);
n 個の要素からなる要素から k の長さの variations の数は
v(n, k) = 1, if k = 0 v(n, k) = n*(n-1)*...*(n-k+1), if 0 < k <= n
variations_with_repetition(\@data, $k)
重複を許す @data の長さ $k の variations とは、@data の要素からなる、重複を許す長さが $k の対の全体である。例えば @data = (1, 2, 3) 及び $k = 2 であれば以下のようになる。
(1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3) (3, 1) (3, 2) (3, 3)
$k は @data の長さより大きくてもよいことに注意すること。例えば @data = (1, 2, 3) 及び $k = 2 であれば以下のようになる。
(1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 2, 2) (2, 1, 1) (2, 1, 2) (2, 2, 1) (2, 2, 2)
n 個の要素からなる、重複を許す長さ k >= 0 の variations の数は
vr(n, k) = n**k
tuples(\@data, $k)
これは上記の variations へのエイリアスである。
tuples_with_repetition(\@data, $k)
これは上記の variations_with_repetition へのエイリアスである。
combinations(\@data, $k)
@data の長さ $k の組み合わせは @data の要素からなる長さ $k の集合全体である。例えば @data = (1, 2, 3, 4) 及び $k = 3 であれば以下のようになる。
(1, 2, 3) (1, 2, 4) (1, 3, 4) (2, 3, 4)
これが意味を持つためには $k は @data の長さ以下でなければならない。
n 個の要素からなる 0 <= k <= n 個の要素の組み合わせの数は
n choose k = n!/(k!*(n-k)!)
combinations_with_repetition(\@data, $k);
@data の重複を許す長さ $k の組み合わせは @data の要素からなる重複を許す長さ $k の集合全体である。例えば @data = (1, 2, 3, 4) 及び $k = 2 であれば以下のようになる。
(1, 1) (1, 2) (1, 3) (2, 2) (2, 3) (3, 3)
$k は @data の長さより大きくてもよい。例えば @data = (1, 2, 3) 及び $k = 4 であれば以下のようになる。
(1, 1, 1, 1) (1, 1, 1, 2) (1, 1, 1, 3) (1, 1, 2, 2) (1, 1, 2, 3) (1, 1, 3, 3) (1, 2, 2, 2) (1, 2, 2, 3) (1, 2, 3, 3) (1, 3, 3, 3) (2, 2, 2, 2) (2, 2, 2, 3) (2, 2, 3, 3) (2, 3, 3, 3) (3, 3, 3, 3)
重複を許す n 個の要素から k >= 0 個を取り出す組み合わせの数は
n+k-1 over k = (n+k-1)!/(k!*(n-1)!)
partitions(\@data[, $k])
@data の partition とは @data を別々の部分に分割することである。技術的には、空でなく、互いに共通部分のないが、それらの結合は @data となるような @data の部分集合に分けることである。例えば @data = (1, 2, 3) の partition は以下のようになる。
((1, 2, 3)) ((1, 2), (3)) ((1, 3), (2)) ((1), (2, 3)) ((1), (2), (3))
このサブルーチンは対の対を返す。最上段の対（配列参照）はその要素が、@data の部分集合を示す対であるような partition それ自身を表す。n 個の要素からなる集合の partition の数はベル数（Bell numbers）として知られ、以下の回帰式を満たす。
B(0) = 1 B(n+1) = (n over 0)B(0) + (n over 1)B(1) + ... + (n over n)B(n)
オプションのパラメータ $k が渡されれば、サブルーチンは大きさ $k の partition のみを生成する。これは既知の大きさの partition を特定するアルゴリズムを利用している。これはあらゆる partition を生成して大きさでふるいにかけるよりも効率的なものである。
部分集合自体がそこそこの大きさになる場合は partition の要素が $k とする。すなわち @data が 5 つの要素を持っているとすれば、大きさ 2 の部分集合を持つ大きさ 2 の partition を持ち、その補数は 3 となる。大きさ 1 の partition の補数は 4 となる。両方の場合ともpartition は同じ大きさ 2 となる。
n 個の要素からなる集合の大きさ k の partition の数は第２種スターリング数（Stirling numbers of the second kind）として知られ、以下の回帰式を満たす。
S(0, 0) = 1 S(n, 0) = 0 if n > 0 S(n, 1) = S(n, n) = 1 S(n, k) = S(n-1, k-1) + kS(n-1, k)
version 0.05 以降はサブルーチンは $k が異常な値でも多少は稼動する。
また、0.05 以降では、空の @datas もサポートしている。
Algorithm::Combinatorics はデフォルトでは何もエクスポートしない。必要に応じてて各サブルーチンをエクスポートすることができる。その場合には以下のように書く。
use Algorithm::Combinatorics qw(combinations);
全てをエクスポートするにはタグ all を用いる。
use Algorithm::Combinatorics qw(:all);
警告
以下の状況下では警告が出る。
エラー
以下の状況下ではエラーが出る。
Algorithm::Combinatorics は Perl 5.6.2. で稼動することは確認されている。テスト用に Test::More 及び FindBin、reftype() 用に Scalar::Util、XS 用に XSLoader を使用している。
バグ報告や機能要望は bug-algorithm-combinatorics@rt.cpan.org または http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Algorithm-Combinatorics まで。
同様の特徴を提供する Perl モジュールに Math::Combinatorics がある。
Xavier Noria (FXN), <fxn@cpan.org>
Copyright 2005-2006 Xavier Noria, all rights reserved.
本プログラムはフリーソフトウェアであり、Perl 本体と同等の条件で修正／再配布してもよい。
|
|
Updated : 2007/10/19 |