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

名称

　Algorithm::ChooseSubsets - リストの部分集合を取り出すオブジェクト指向インタフェース

概要

use Algorithm::ChooseSubsets

# 集合の全部分集合を選ぶ
$i = new Algorithm::ChooseSubsets($n);  
$i = new Algorithm::ChooseSubsets(\@set);  
$i = new Algorithm::ChooseSubsets(set=>\@set);

# 固定の大きさ $k の部分集合を選ぶ
$i = new Algorithm::ChooseSubsets($n,$k);
$i = new Algorithm::ChooseSubsets(\@set,$k);
$i = new Algorithm::ChooseSubsets(set=>\@set, size=>$k);

# k 以上の大きさの部分集合を選ぶ
$i = new Algorithm::ChooseSubsets($n,$k,1);
$i = new Algorithm::ChooseSubsets(\@set,$k,1);
$i = new Algorithm::ChooseSubsets(set=>\@set, size=>$k, all=>1);

while ($x = $i->next) {
	# @$x で何か処理する。
}

$i->reset;        # 最初の部分集合を返す

説明

　この文脈における「部分集合」は元リストから要素を選んだリストへの参照であり、元リストと同じ順にならんだものである。オブジェクトが生成されると、next() を呼び出すたびに辞書的順序に従って部分集合を返す（元リストがアルファベットの場合）。
　K が指定されれば、その大きさの部分集合のみを返す。K が省略されれば、空集合から元集合までの全ての部分集合を返す。'all'フラグと 'K' が指定されれば大きさが K 以上の全ての部分集合を返す。
　リストの替わりに数字 N が指定されればリストは [0..N-1] からとられる。

使用例

# ab ac ad ae bc bd be cd ce de を出力
$i = new Algorithm::ChooseSubsets([qw(a b c d e)],2);
print @$x," " while ($x = $i->next);

# ポーカーの 2,598,960 種類の全ての手を出力
$i = new Algorithm::ChooseSubsets (\@cards, 5);
print @$hand,"\n" while ($hand = $i->next);

# ::0:1:2:01:02:12:012 を出力
$i = new Algorithm::ChooseSubsets(3);
print ":",@$j while ($j = $i->next);

注釈

　固定された K に対し、next() は N! / (K! * [N-K]!) 回答えを返す。
　大きさ N のリストの全部分集合は 2**N 回値を返す。

著者

　Brian Duggan, <bduggan@matatu.org>

参考資料

　perl(1).

Updated : 2006/06/23