組み合わせを作るアルゴリズム

質問

アルゴリズムについてうまい考えが浮かばず、お知恵を拝借できればと思い質問致しました。
要件は、値が１００個ほど入った配列があり、この配列から任意の個数の値を取り出して処理をする、というものなのですが、とにかく全ての組み合わせを取り出したいのです。
例えば
@data = (3, 6, 8, 6);
という配列から２個取り出すとすれば、
(3, 6)
(3, 8)
(3, 6)
(6, 8)
(6, 6)
(8, 6)
という全６パターンが欲しいのです。（パターンの出現順は無視できます。）
順番違いはなくてよいので、たとえば (6, 3) というリストはなくて結構です。
また (3, 6) のように、全く同じリストが複数出現してもＯＫです。

取り出す個数が固定ならばforループのネストで処理のしようもあるのですが、任意ということでここの処理方法が浮かびません。
（ちなみにrは最大で１０まで取り、できればforのネストも避けたいところなのですが。）
このような処理に適した処理方法をご存知の方おられましたら、ぜひともご教授ください。
よろしくお願い致します。

回答No.4

leaz024 · ベストアンサー

No.3-osamuyさんの
> このやり方で100C10を実行すると、うちのiBookでは、約７年半ほどかかります。
についてですが、一般的に再帰は速度とメモリ効率に難があり、それを思ってNo.2で再帰ではないコードを載せたんですが、ちとミスをしており、速度に関してあまり効果が上がっていませんでした。

ミスというのは、頻繁に起きるループからの脱出に goto を使っている点です。
ループからの脱出では「スタックの復帰処理」などをするのですが、gotoは汎用ジャンプ関数のためこれが遅く、足を引っ張られていました。
以下のように変えると、かなり速くなります。

LOOP_TOP:
　　while (1) {
　　　　$func->(@cnt);
　　　　for (my $i = 0; $i <= $r; $i++) {
　　　　　　if ($cnt[$r-$i] < $n-$i) {
　　　　　　　　$cnt[$r-$i]++;
　　　　　　　　$cnt[$r-$i] = $cnt[$r-$i-1]+1 while $i--;
　　　　　　　　redo LOOP_TOP;
　　　　　　}
　　　　}
　　　　last;
　　}

お礼

ご回答ありがとうございます。
お礼をする前に２件頂いてしまいましたので、こちらにまとめさせて頂きます。
初めは何の処理をしているのか分かりませんでしたが、@cntをループごとに書き出してみたところ、理解することができました。
速度に関して再度ご投稿を頂きましたので、#2、#3、#4のコードを同様の条件の元に書き直しベンチマークを取ったところ、確かに#4のコードが１番でした。
（#2と#3については、rやnが小さいうちは#3の方が速く、大きくなるにつれ#2の方が速くなるようです。）
gotoやredoなどの内部処理については全くの無知でしたので、大変参考になりました。
どうもありがとうございました。

回答No.3

osamuy

CPANに、順列／組み合わせを生成するモジュールがあるので、そちらを使うのが手っ取り早いのですが、頭の体操として。
一般的に、この手のものは再帰（recursion）を使うと、簡単に実現できます。
こんな感じ：

sub combinatorial {
my( $n, $r, $result_set ) = @_;
if ( $r == 0 ){
print join( ', ', @$result_set ), "\n";
return;
}
my $start = $result_set->[ $#$result_set ];
$start += defined $start ? 1 : 0;
my $end = $n - $r;
for ( my $i = $start; $i <= $end; $i++ ){
push @$result_set, $i;
&combinatorial( $n, $r - 1, $result_set );
pop @$result_set;
}
}

&combinatorial( 5, 3, [] );

このやり方で100C10を実行すると、うちのiBookでは、約７年半ほどかかります。

お礼

ご回答ありがとうございます。
なるほど、再帰という手がありましたね。
#2のleaz024さんの回答もそうでしたが、@dataに適用する添え字のリストを生成するのですね。
大変参考になりました。
どうもありがとうございました。

回答No.2

leaz024

そのような可変型のループでは、
・各ループのカウンタを配列に持つ
・各カウンタの状態管理と更新を行うロジックを書く
とよいでしょう。
また、@dataから直接データを取り出すようにするのではなく、n個の配列からr個を取り出す「取り出し方」を生成し、その取り出し方を作業関数に渡すようにするとよいでしょう。
以下は、「７個の配列から４個の値を取り出して処理する」サンプルです。
※関数workは、7Ｃ4 = 35 回実行されます。

my @data = (0, 3, 6, 8, 6, 9, 7);
combi($#data+1, 4, \&work);　　　　# 作業関数も渡す

# 組み合わせ（nＣr）のパターンを作り、１つずつ作業関数に渡す汎用関数
sub combi {
　　my ($n, $r, $func) = @_;
　　$n--; $r--;　　　　　　　　　　　　# 記述簡略化のため１引いておく

　　my @cnt = (0 .. $r);　　　　　　　# ループカウンタ（組み合わせパターン）を初期化
LOOP_TOP:
　　$func->(@cnt);　　　　　　　　　　# 組み合わせごとに作業関数を呼び出す
　　for (my $i = 0; $i <= $r; $i++) {
　　　　if ($cnt[$r-$i] < $n-$i) {　　　　　　　# $r-$i番目のカウンタは更新可能か
　　　　　　$cnt[$r-$i]++;　　　　　　　　　　　　　　　　　　# $r-$i番目のカウンタを更新
　　　　　　$cnt[$r-$i] = $cnt[$r-$i-1]+1 while $i--;　　# それより後ろのカウンタを初期化
　　　　　　goto LOOP_TOP;
　　　　}
　　}
　　# 全てのカウンタが更新できなければ終了
}

# 作業関数
sub work {
　　print "@data[@_]\n";　　　　# 組み合わせを表示
}

回答No.1

riyop

perlでしょうか、、、

$n = @data;
for($i=0;$i<$n;$i++){
for($j=$i+1;$j<$n;$j++){
print "($i,$j)\n"
}
}

これでどうでしょうか。（未確認ですが）

補足

ご回答ありがとうございます。
質問では要素４個の配列から２個を取り出す組み合わせを挙げましたが、実際には要素数は１００個ほどあり、取り出す値も最大１０まで（場合によって変わります）あるので、for文のネストでは処理が難しいのです。
何か良い処理方法がありましたら、またお願い致します。