![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?5a7ff87)
![](http://oshiete.xgoo.jp/images/v2/common/profile/M/noimageicon_setting_12.png?5a7ff87)
アルゴリズムについてうまい考えが浮かばず、お知恵を拝借できればと思い質問致しました。
要件は、値が100個ほど入った配列があり、この配列から任意の個数の値を取り出して処理をする、というものなのですが、とにかく全ての組み合わせを取り出したいのです。
例えば
@data = (3, 6, 8, 6);
という配列から2個取り出すとすれば、
(3, 6)
(3, 8)
(3, 6)
(6, 8)
(6, 6)
(8, 6)
という全6パターンが欲しいのです。(パターンの出現順は無視できます。)
順番違いはなくてよいので、たとえば (6, 3) というリストはなくて結構です。
また (3, 6) のように、全く同じリストが複数出現してもOKです。
取り出す個数が固定ならばforループのネストで処理のしようもあるのですが、任意ということでここの処理方法が浮かびません。
(ちなみにrは最大で10まで取り、できればforのネストも避けたいところなのですが。)
このような処理に適した処理方法をご存知の方おられましたら、ぜひともご教授ください。
よろしくお願い致します。
No.4ベストアンサー
- 回答日時:
No.3-osamuyさんの
> このやり方で100C10を実行すると、うちのiBookでは、約7年半ほどかかります。
についてですが、一般的に再帰は速度とメモリ効率に難があり、それを思って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;
}
ご回答ありがとうございます。
お礼をする前に2件頂いてしまいましたので、こちらにまとめさせて頂きます。
初めは何の処理をしているのか分かりませんでしたが、@cntをループごとに書き出してみたところ、理解することができました。
速度に関して再度ご投稿を頂きましたので、#2、#3、#4のコードを同様の条件の元に書き直しベンチマークを取ったところ、確かに#4のコードが1番でした。
(#2と#3については、rやnが小さいうちは#3の方が速く、大きくなるにつれ#2の方が速くなるようです。)
gotoやredoなどの内部処理については全くの無知でしたので、大変参考になりました。
どうもありがとうございました。
No.3
- 回答日時:
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では、約7年半ほどかかります。
ご回答ありがとうございます。
なるほど、再帰という手がありましたね。
#2のleaz024さんの回答もそうでしたが、@dataに適用する添え字のリストを生成するのですね。
大変参考になりました。
どうもありがとうございました。
No.2
- 回答日時:
そのような可変型のループでは、
・各ループのカウンタを配列に持つ
・各カウンタの状態管理と更新を行うロジックを書く
とよいでしょう。
また、@dataから直接データを取り出すようにするのではなく、n個の配列からr個を取り出す「取り出し方」を生成し、その取り出し方を作業関数に渡すようにするとよいでしょう。
以下は、「7個の配列から4個の値を取り出して処理する」サンプルです。
※関数workは、7C4 = 35 回実行されます。
my @data = (0, 3, 6, 8, 6, 9, 7);
combi($#data+1, 4, \&work); # 作業関数も渡す
# 組み合わせ(nCr)のパターンを作り、1つずつ作業関数に渡す汎用関数
sub combi {
my ($n, $r, $func) = @_;
$n--; $r--; # 記述簡略化のため1引いておく
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
- 回答日時:
perlでしょうか、、、
$n = @data;
for($i=0;$i<$n;$i++){
for($j=$i+1;$j<$n;$j++){
print "($i,$j)\n"
}
}
これでどうでしょうか。(未確認ですが)
この回答への補足
ご回答ありがとうございます。
質問では要素4個の配列から2個を取り出す組み合わせを挙げましたが、実際には要素数は100個ほどあり、取り出す値も最大10まで(場合によって変わります)あるので、for文のネストでは処理が難しいのです。
何か良い処理方法がありましたら、またお願い致します。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- PHP 配列の値の更新方法について 1 2022/08/05 09:49
- Java Java 南京錠 2 2023/02/04 11:46
- 分譲マンション 分譲マンションの管理組合・理事長です。この難しい件はどうすれば良いでしょうか? 9 2022/07/20 01:23
- Visual Basic(VBA) 前回ご教授いただいたコードに覚えたてのループ処理で品名りんごAから順に20回for nextでループ 7 2023/01/13 22:01
- C言語・C++・C# numpyスライス機能を使った数値計算 2 2023/05/08 16:01
- JavaScript カラーミーショップのsectionループ内で、[引数][戻り値]ありの関数的な処理を行いたいです。 1 2022/05/07 19:39
- Visual Basic(VBA) vba 等間隔の列に対しての計算 6 2022/05/17 20:15
- 飲食店・レストラン バイキング店での無法行為(割込み、人気料理だけ独り占めする客) どうしたらいい? 7 2023/03/22 18:41
- Excel(エクセル) excelにて、ある固定値から連番を振りたいが、上限値が異なる連番を振る処理を複数回行いたい場合 6 2022/10/22 11:01
- Ruby 初心者プログラミング 3 2022/10/12 11:31
関連するカテゴリからQ&Aを探す
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
データベースから取得したデー...
-
index関数で複数個抜き出す
-
perlで2つの配列を比較する方...
-
VBのReturnの使い方
-
画面を強制的に再描画させる方法
-
範囲指定したセルを1つずつ飛...
-
VBAで3秒だけ時間を止めたい
-
VBAでの一時停止と再開の方法
-
DoEventsが必要な理由について
-
vbscriptでIE自動入力(途中で...
-
DOSコマンドのループ内のTIMEコ...
-
Escキーを押すと、中断する時と...
-
流れ図(フローチャート)が分か...
-
ハッシュマーク以降のアドレス取得
-
再帰関数のインライン展開
-
Excel vba でコンボボックスの...
-
リストボックスに縦スクロール...
-
UWSCに制限時間を付けたいです
-
vb.netです。2次元配列の要素を...
-
forループは何故、forなのですか?
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
データベースから取得したデー...
-
perlで2つの配列を比較する方...
-
perlでファイルの拡張子を除い...
-
python質問
-
QNo.3258883データベースから取...
-
組み合わせを作るアルゴリズム
-
非共通要素を抜き出す
-
アルファベットn文字の組み合わ...
-
grep関数を用いた複数行からの抽出
-
複数の配列の要素を繰り返し処...
-
桁数指定と四捨五入
-
ハッシュのハッシュの値代入で...
-
サブルーチンへ渡した配列のリ...
-
index関数で複数個抜き出す
-
二次元配列のつかいかた。
-
正規表現 perl 連続ヒットの...
-
配列に入った変数を二度使いたい
-
プログラミングについて。 1つ...
-
画面を強制的に再描画させる方法
-
VBのReturnの使い方
おすすめ情報