Location : Home > Languages > Perl > Package
Title : Math::Combinatorics
 		Toolbox Logo

名称

　Math::Combinatorics - リストの順列・組み合わせの計算

概要

Available as an object oriented API.

use Math::Combinatorics;

my @n = qw(a b c);
my $combinat = Math::Combinatorics->new(count => 2,
               data => [@n],
              );

print "combinations of 2 from: ".join(" ",@n)."\n";
print "------------------------".("--" x scalar(@n))."\n";
while(my @combo = $combinat->next_combination){
   print join(' ', @combo)."\n";
}

print "\n";

print "permutations of 3 from: ".join(" ",@n)."\n";
print "------------------------".("--" x scalar(@n))."\n";
while(my @permu = $combinat->next_permutation){
   print join(' ', @permu)."\n";
}

出力：

'permute', 'combine', 'factorial' などの関数を用いて

use Math::Combinatorics;

my @n = qw(a b c);
print "combinations of 2 from: ".join(" ",@n)."\n";
print "------------------------".("--" x scalar(@n))."\n";
print join("\n", map { join " ", @$_ } combine(2,@n)),"\n";
print "\n";
print "permutations of 3 from: ".join(" ",@n)."\n";
print "------------------------".("--" x scalar(@n))."\n";
print join("\n", map { join " ", @$_ } permute(@n)),"\n";

出力：

combinations of 2 from: a b c
------------------------------
a b
a c
b c

permutations of 3 from: a b c
------------------------------
a b c
a c b
b a c
b c a
c a b
c b a

　どちらのタイプの呼び出しも出力は同じであるが、オブジェクト指向アプローチのほうが大規模な集合に対して小さいメモリしか消費しない。

説明

　組み合わせ論は集合の要素の列挙・組み合わせ・順列及びそれらの属性を特徴付ける数学的関係を研究する数学の一分野である。詳しくは次を見よ。http://mathworld.wolfram.com/Combinatorics.html

　本モジュールは nCk, nCRk, nPk, nPRk, !n, n! （それぞれ、組み合わせ・重複組み合わせ・順列・文字列・攪乱・階乗を意味する）の Perl のみによる実装を提供する。関数による使用法及びオブジェクト指向的使用法が用いることができる。

組み合わせ（combine） - nCk

http://mathworld.wolfram.com/Combination.html

　ピザ屋の店員を困らせる楽しい質問。「ピザのトッピングを２種類するとして、どれだけの組み合わせができますか？」

攪乱（derange） - !n

http://mathworld.wolfram.com/Derangement.html

　n 個のオブジェクトの攪乱は、!n で表され、自然な（順序はそのままで）全てが現れる順列の個数である。

permute - nPk

http://mathworld.wolfram.com/Permutation.html

　マスター・マインド・ゲーム：色の重複なしである位置の番号の色を当てる方法。
　frequency ベクトルとともに new() を呼び出すことでこれらの問題をオブジェクト指向風に処理することができる。

string - nPRk

http://mathworld.wolfram.com/String.html

　モールス信号：２つの記号 - と . を用いて３つの異なる位置に格納する方法。

$o = Math::Combinatorics->new( count=>3 , data=>[qw(. -)] , frequency=>[3,3] );
while ( my @x = $o->next_multiset ) {
   my $p = Math::Combinatorics->new( data=>\@x , frequency=>[map{1} @x] );
   while ( my @y = $p->next_string ) {
     # 何か処理を
   }
}

multiset/multichoose - nCRk

http://mathworld.wolfram.com/Multiset.html

　３個の黒球と３個の白球が入ったバッグから１度に３個取り出す方法。

$o = Math::Combinatorics->new( count=>3 , data=>[qw(white black)] , frequency=>[3,3] );
while ( my @x = $o->next_multiset ) {
   # 何か処理を
}

エクスポート

　以下エクスポートタグは呼び出し側の名前空間に単一メソッドとして持ち込まれる。デフォルトではエクスポートしない。各メソッドの記述については POD ドキュメントを見よ。

combine
derange
multiset
permute
string
factorial

著者

　Allen Day <allenday@ucla.edu>, Christopher Eltschka 及び Tye からはアルゴリズムに関して貢献してくれた。

　Copyright (c) 2004-2005 Allen Day. All rights reserved.

　本プログラムはフリーソフトウェアであり、Perl 本体と同等の条件で修正／再配布してもよい。

謝辞

　本モジュールをよりよくするために貢献していただいた全ての方に感謝する。最初に公開して以来、パッチや改善を受け取ることができた。Math::Combinatorics はコミュニティにより開発され、改善していく。貢献者は以下の通り。
新機能の追加：Carlos Rica, David Coppit, Carlos Segre, Lyon Lemmens
バグ報告をしてくれた方： Ying Yang, Joerg Beyer, Marc Logghe, Yunheng Wang, Torsten Seemann, Gerrit Haase, Joern Behre, Lyon Lemmens, Federico Lucifredi

Bugs / To Do

　著者に知らせて欲しい。

参考資料

エクスポート関数

combine()

使用法：my @combinations = combine($k,@n);
関数： nCk または n!/(k!*(n-k)!) を実装しており、n 個の要素からなる集合から k 個の要素を抽出するあらゆる組み合わせを返す。n 個の項目はキャラクタデータと仮定されており、返すデータ構造にコピーされる。（後述の「返り値」を見よ。）
使用例： 
my @n = qw(a b c);
my @c = combine(2,@n);
print join "\n", map { join " ", @$_ } @c;
# 出力は
# b c
# a c
# a b
返り値：n 個から k 個抽出する組み合わせを含む配列のリスト。
引数：組み合わされる要素のリスト。
注意：データは内部的に英数字として処理される。これは大きな集合の組み合わせを生成する際に効率的になるため必要である。非英数字データの組み合わせやデータソート {$a cmp $b} は適切ではなく、オブジェクト指向APIを用いること。new() 及び compare オプションを見よ。
同一の項目はユニークでないと見なされる。すなわち combine(1,'a','a') を呼び出すと、２つの集合 {a}, {a} を得る。これが望む振る舞いでないならば next_multiset() を見よ。

derange()

使用法：my @deranges = derange(@n);
関数：!n の実装。すなわち元の場所に現れる項目が１つもない n 個の要素の攪乱。
使用例： 
my @n = qw(a b c);
my @d = derange(@n);
print join "\n", map { join " ", @$_ } @d;

# 出力は
# a c b
# b a c
# b c a
# c a b
# c b a
返り値：n 個から k 個を抽出する（ただし k == n）攪乱を含む配列のリスト。
引数：攪乱される要素のリスト。
注意：k はパラメータ化されていなければならない。これは後のバージョンでなされるだろう。これを実装するパッチを送ってくれ。
注意：データ内部的に英数字として処理される。これは大きな集合の組み合わせを生成する際に効率的になるため必要である。非英数字データの組み合わせやデータソート {$a cmp $b} は適切ではなく、オブジェクト指向APIを用いること。new() 及び compare オプションを見よ。
同一の項目はユニークでないと見なされる。すなわち combine(1,'a','a') を呼び出すと、２つの集合 {a}, {a} を得る。これが望む振る舞いでないならば next_multiset() を見よ。

factorial()

使用法：my $f = factorial(4); # 24 または 4*3*2*1 を返す。
関数：n! （n の階乗）を計算する。
返り値：n が非整数 または n < 0 であれば undef を返す。
引数：正で非負の整数。
注意：この関数は combine() 及び permute() で内部的に用いられる。

permute()

使用法：my @permutations = permute(@n);
関数：nPk（ただしk==n） または n!/(n-k)! を実装しており、n 個の要素からなる集合から k 個の要素を抽出するあらゆる順列を返す。（ただし n == k である。下記の「注意」を見よ。）
n 個の項目はキャラクタデータと仮定されており、返すデータ構造にコピーされる。
使用例： 
my @n = qw(a b c);
my @p = permute(@n);
print join "\n", map { join " ", @$_ } @p;

# 出力は
# b a c
# b c a
# c b a
# c a b
# a c b
# a b c
返り値：n 個から k 個抽出する順列を含む配列のリスト。（ただし k == n）
引数： 組み合わされる要素のリスト。
注意：k はパラメータ化されていなければならない。これは後のバージョンでなされるだろう。これを実装するパッチを送ってくれ。
注意：データ内部的に英数字として処理される。これは大きな集合の組み合わせを生成する際に効率的になるため必要である。非英数字データの組み合わせやデータソート {$a cmp $b} は適切ではなく、オブジェクト指向APIを用いること。new() 及び compare オプションを見よ。 同一の項目はユニークでないと見なされる。すなわち permute('a','a') を呼び出すと、２つの集合 {a,a}, {a,a} を得る。これが望む振る舞いでないならば next_string() を見よ。

コンストラクタ

new()

使用法： 
my $c = Math::Combinatorics->new( count => 2,        # int として扱う
            data => [1,2,3,4] # 匿名の配列への配列参照
            );
関数：新たな Math::Combinatorics オブジェクトを生成する。
返り値：Math::Combinatorics オブジェクト
引数：
  • count : 組み合わせ関数／メソッドで用いられる。返される集合の要素の数である。
  • data : 組み合わせ及び順列の関数／メソッドで用いられる。これは選ばれる要素の集合である。注意：この配列は順に変更される。呼び出す順番が呼び出し側で問題になるのであれば配列のコピーをとっておくこと。
  • frequency : データ頻度のオプションベクトル。data コンストラクタ引数と同じ長さでなければならない。以下の２つのコンストラクタ呼び出しは同値である。
$a = 'a';
$b = 'b';

Math::Combinatorics->new( count=>2, data=>[\$a,\$a,\$a,\$a,\$a,\$b,\$b] );
Math::Combinatorics->new( count=>2, data=>[\$a,\$b], frequency=>[5,2] );

　なぜこのようにするのか？　複数の同じよそを利用するほうが有用な場合があるからだ。（組み合わせ論のジャーゴンでは「バッグ（bag）」と言う。Set::Bag を見よ。）

  • compare - 集合の要素をソートする際に参照されるオプションのサブルーチン。

　例えば

# キャラクター要素に適切
compare => sub { $_[0] cmp $_[1] }
# 数値要素に適切
compare => sub { $_[0] <=> $_[1] }
# たぶんオブジェクト要素に適切
compare => sub { $_[0]->value <=> $_[1]->value }

　デフォルトのソート機構は参照に基づいており、予言できるものではない。さらに柔軟な compare() 機構があれば歓迎する。

オブジェクトメソッド

next_combination()

使用法：my @combo = $c->next_combination();
関数：@data から $count の組み合わせを取得する。
返り値： @data から $count 項目の組み合わせを返す。（new() を見よ）
繰り返し呼び出すと、そのたびにユニークな $count 個の要素からなる組み合わせを生成する。空のリストは全ての組み合わせが出力されたことを意味する。
注意：本メソッドは引数が new() によって与えられた場合にのみ用いること。それ以外は next_multiset() を用いること。
引数：なし。

next_derangement()

使用法：my @derangement = $c->next_derangement();
関数：@data から攪乱を取得する。
返り値：@data から１つも同じ場所に現われない順列を返す。（new() を見よ）
繰り返し呼び出すと @data 要素のあらゆる攪乱を取得することができる。空のリストは全ての攪乱が出力されたことを示す。
引数：なし。

next_multiset()

使用法：my @multiset = $c->next_multiset();
関数：@data から multisets を取得する。
返り値：@data から要素の multiset を返す。（new() を見よ）
multiset とは組み合わせの特別な型で互いに区別できない要素を含む組み合わせのことである。new() に frequency 引数が渡されたときには next_multiset() を用いること。繰り返し呼び出すと @data 要素のあらゆる multiset を取得することができる。空のリストは全て出力されたことを示す。
注意：本メソッドは frequency 引数が new() に渡されたときのみ使用される。それ以外の場合は next_combination() を用いる。
引数：なし。

next_permutation()

使用法：my @permu = $c->next_permutation();
関数：@data から順列を取得する。
返り値：@data から順列を返す。（new() を見よ）
繰り返し呼び出すと @data 要素のあらゆる順列を取得することができる。空のリストは全て出力されたことを示す。
注意：本メソッドは frequency 引数が new() に渡されなかったときのみ使用される。それ以外の場合は next_string() を用いる。
引数：なし。

next_string()

使用法：my @string = $c->next_string();
関数：@data から文字列を取得する。
返り値：@data から multiset を返す。（new() を見よ）
multiset とは組み合わせの特別な型で互いに区別できない要素を含む組み合わせのことである。new() に frequency 引数が渡されたときには next_permutation() を用いること。繰り返し呼び出すと @data 要素のあらゆる multiset を取得することができる。空のリストは全て出力されたことを示す。
注意：本メソッドは frequency 引数が new() に渡されたときのみ使用される。それ以外の場合は next_permutation() を用いる。
引数：なし。

内部関数とメソッド

sum()

使用法：my $sum = sum(1,2,3); # ６を返す
関数：整数のリストの総和。非整数は無視される。
返り値：渡された引数に含まれる整数の和。
引数：整数のリスト
注意：この関数は combine() により内部で使用される。

compare()

使用法：$obj->compare()
関数：内部で稼動し、ドキュメント化はまだ。比較するコード参照を保持する。
返り値：比較の値（コード参照）

count()

使用法：$obj->count()
関数：内部で稼動し、ドキュメント化はまだ。 nCk や nPk における k を保持する。
返り値：カウント数（整数）

data()

使用法：$obj->data()
関数：内部で稼動し、ドキュメント化はまだ。 nCk や nPk における n を保持する。
返り値：データの値（配列参照）

swap()

　内部で稼動し、ドキュメント化はまだ。

reverse()

　内部で稼動し、ドキュメント化はまだ。

rotate()

　内部で稼動し、ドキュメント化はまだ。

upper_bound()

　内部で稼動し、ドキュメント化はまだ。

lower_bound()

　内部で稼動し、ドキュメント化はまだ。

_permutation_cursor()

使用法：$obj->_permutation_cursor()
関数：内部メソッド。繰り返し演算のカーソル。
返り値：_permutation_cursor の値（配列参照）
引数：なし。
Toolbox Logo
 Updated : 2007/07/17