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


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をいただければとてもうれしいです。

回答の条件
  • 1人2回まで
  • 登録:2008/08/25 01:56:51
  • 終了:2008/08/28 21:50:01

ベストアンサー

id:imo758 No.2

imo758回答回数121ベストアンサー獲得回数192008/08/25 12:55:51

ポイント98pt

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

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
id:biz_tanaka

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

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

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

2008/08/26 13:38:08

その他の回答(1件)

id:ayucat_on_tabelog No.1

ayucat回答回数11ベストアンサー獲得回数12008/08/25 07:29:25

ポイント60pt

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

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

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

id:biz_tanaka

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

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

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

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

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

2008/08/25 09:49:28
id:imo758 No.2

imo758回答回数121ベストアンサー獲得回数192008/08/25 12:55:51ここでベストアンサー

ポイント98pt

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

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
id:biz_tanaka

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

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

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

2008/08/26 13:38:08
  • id:Mook
    50個もの数値の組み合わせをすべて列挙するのはけっこう大変ですよ。

    50個中25個を使用する場合だけでも、100兆以上の組み合わせになり、全体の
    組み合わせの数は2の50乗個です。

    考え方は、下記が参考になるでしょう。
    http://ja.wikipedia.org/wiki/%E7%B5%84%E5%90%88%E3%81%9B_(%E6%95%B0%E5%AD%A6)
  • id:rsc96074
    C言語アルゴリズム辞典の「組合せ生成」プログラムをDOS窓で試したら、制御不能になって、DOS窓を閉じました。(汗;
    http://www.saiensu.co.jp/?page=book_details&ISBN=ISBN978-4-7819-0548-8&YEAR=1989
    上の本あたりにあるのでは。
  • id:i_kumagoro
    (1番目の回答のように)再帰を使わなければ、算出に必要なメモリはたかが知れています。コメントにある

    > 負荷的に厳しい

    というのが時間的な問題を指しているのであれば、改善は難しいと思います。少なくともC言語では、算出よりも結果の出力の方がはるかに時間がかかるはずです。また、算出にかかる時間が限りなくゼロに近づいたとしても、出力されるデータ量が膨大過ぎる(仕様なのでどうやっても覆りません)という点において極めて非実用的なプログラムにしかならないと思います。
    例えば、50個中25個を使用する、100兆組分の組み合わせを出力(これでも全体の出力からすれば一部分です)しようとすると7000テラバイト以上のデータになります。
  • id:biz_tanaka
    biz_tanaka 2008/08/28 21:48:53
    コメント、ありがとうございました。

    たしかに、算出は大変なことになりました。。。が、今回は実験用のプログラムで、ロジックの見通しを作ることが優先でしたので、いただいたご回答、コメントにて十分こちらの目的を達することができました。

この質問への反応(ブックマークコメント)

トラックバック

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません