人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

総当たりのアルゴリズムについて教えてください。

0から49までの数字があるとし、その数字のすべての組み合わせのパターンを出力したいと考えています。
組み合わせが1要素の場合、出力は次のようになります。
0
1
2
...(中略)...
48
49

組み合わせが2要素の場合、次のようになります。
0,1
0,2
...(中略)...
0,48
0,49
1,2
1,3
...(中略)...
1,48
1,49
...(中略)...
47,48
47,49
48,49

組み合わせが3要素の場合、次のようになります。
0,1,2
0,1,3
0,1,4
...(中略)...
0,1,48
0,1,49
0,2,3
0,2,4
...(中略)...
47,48,49

このように、組み合わせの要素数を50まで増やしながら、すべての組み合わせを出力するにはどのようなロジックを考えればよいでしょうか?
なお、組み合わせ作成時において、
0,1 と 1,0
0,1,2 と 2,1,0
のように、順番が異なるだけの数字については、同じ組み合わせと判断し、重複が取り除かれていることを期待します。

スクリプトのソースコードや参考URLをいただければとてもうれしいです。


●質問者: biz_tanaka
●カテゴリ:コンピュータ 科学・統計資料
✍キーワード:URL アルゴリズム スクリプト ソースコード パターン
○ 状態 :終了
└ 回答数 : 2/2件

▽最新の回答へ

1 ● ayucat
●60ポイント

http://www5.airnet.ne.jp/tomy/cpro/perm.htm

こちらに順列の場合と組み合わせの場合のコードが掲載されています。

No2のほうをお使いになるといいと思います。

◎質問者からの返答

ご回答ありがとうございました。

実は、我流で再帰を使った総当たり組み合わせを作るスクリプトを書いてみたのですが、猛烈なパターン数のためにメモリがいくらあっても足りませんでした(Linuxでセグメンテーションフォルトになります)。そこで、少しでも効率的に処理できるようにするために、公式的なロジックがあれば知りたいと思い質問させていただいた次第です。

いただいたサンプル、ありがとうございました。

試してみたいと思います。

ただ、ソースコードを拝見するに、やはり組み合わせパターン数が多い場合は負荷的に厳しいかもしれませんね。


2 ● imo758
●98ポイント ベストアンサー

これで大丈夫なのかな…と

Perl 5

#!/usr/local/bin/perl
use strict;
use warnings;
our $number = 50;
our $test_flag = 0;

reflex('', 1, $number) if $test_flag;
for(my $rest = 1; $rest <= $number; $rest++){
reflex('', 1, $rest);
}
sub reflex{
my($computed, $start, $rest) = @_;
if($rest == 1){
for(my $i = $start; $i <= $number; $i++){
print "$computed$i\n";
}
return;
}else{
$rest--;
my $end = $number - $rest;
for(my $i = $start; $i <= $end; $i++){
reflex("$computed$i,", $i + 1, $rest);
}
}
}
出力例(部分)
2,7,20,37
2,7,20,38
2,7,20,39
2,7,20,40

c言語。スタックがそれなりに要求されることに注意してください。あととても行儀悪い書き方してます。コンパイラによっては通らないかも。

#include <stdio.h>
#define number 50
#define strings_stack 1500 /* だいたい(桁数+1) * number */
#define test_flag 0

void reflex(char *computed, int start, int rest){
if(rest == 1){
int i;
for(i = start; i <= number; i++){
printf("%s%d\n", computed, i);
}
return;
}else{
char computed_stack[strings_stack];
int end;
int i;
rest--;
end = number - rest;
for(i = start; i <= end; i++){
sprintf(computed_stack, "%s%d,", computed, i);
reflex(computed_stack, i + 1, rest);
}
}
}

void main(void){
int rest;
char temp[strings_stack];
if(test_flag == 1){
reflex(temp, 1, number);
return;
}
for(rest = 1; rest <= number; rest++){
reflex(temp, 1, rest);
}
}
コンパイル例 LSI C-86 Ver.3.30 試食版にて
lcc conbi.c -k'-s f000'

出力例(部分)
9,21,41,49
9,21,41,50
9,21,42,43
9,21,42,44
◎質問者からの返答

最初のperlが非常に美しく実装されていて勉強になりました。

ありがとうございました。

Cについてはこれから試してみます。

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ