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

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

配列A ["A1","A2","A3"] と
配列B ["B1","B2","B3"] が与えられたとき、
["A1-B1","A1-B2","A1-B3","A2-B1","A2-B2","A2-B3","A3-B1","A3-B2","A3-B3"] を返すプログラムで、
配列が下の例のように増えても総当たりの一次配列を返すロジックが知りたいです。
配列のフォーマットは一次配列のみですが、各配列の要素数は可変とします。
また、増える配列の数は上限なしとします。

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


例)
配列A ["A1","A2","A3"] と
配列B ["B1","B2","B3"] と
配列C ["C1","C2","C3","C4"] が与えられたとき、
["A1-B1-C1","A1-B1-C2","A1-B1-C3","A1-B1-C4"
"A1-B2-C1","A1-B2-C2","A1-B2-C3","A1-B2-C4"
"A1-B3-C1","A1-B3-C2","A1-B3-C3","A1-B3-C4"
"A2-B1-C1","A2-B1-C2","A2-B1-C3","A2-B1-C4"
"A2-B2-C1","A2-B2-C2","A2-B2-C3","A2-B2-C4"
"A2-B3-C1","A2-B3-C2","A2-B3-C3","A2-B3-C4"
"A3-B1-C1","A3-B1-C2","A3-B1-C3","A3-B1-C4"
"A3-B2-C1","A3-B2-C2","A3-B2-C3","A3-B2-C4"
"A3-B3-C1","A3-B3-C2","A3-B3-C3","A3-B3-C4"] を返す。

配列A ["A1","A2","A3"] と
配列B ["B1","B2","B3"] と
配列C ["C1","C2","C3","C4"] と
配列D ["D1","D2","D3"] が与えられたとき、
["A1-B1-C1-D1","A1-B1-C1-D2","A1-B1-C1-D3",
"A1-B1-C2-D1","A1-B1-C2-D2","A1-B1-C2-D3",
...
"A3-B3-C4-D1","A3-B3-C4-D2","A3-B3-C4-D3"] を返す。


●質問者: biz_tanaka
●カテゴリ:コンピュータ 学習・教育
✍キーワード:A1 A3 b2 C3 D1
○ 状態 :終了
└ 回答数 : 2/2件

▽最新の回答へ

1 ● khoshi3
●40ポイント ベストアンサー

記載された配列の結果を見ると、総当たりのアルゴリズムというより「直積」みたいな感じですね。意外と簡単に以下のような感じで良いのではと思います。(言語が指定されていませんでしたのでとりあえずperlで書きました。):

% cat ./product.pl
#!/usr/bin/perl

sub mul {
 my ($a, $b) = @_;
 my $c;
 foreach my $xa (@$a) {
 foreach my $xb (@$b) {
 push(@$c, $xa . '-' . $xb);
 }
 }
 return $c;
}

$a = ['A1', 'A2', 'A3'];
$b = ['B1', 'B2'];
$c = ['C1', 'C2', 'C3', 'C4'];

# 直積実行
my $ans = mul($a, $b); ## ans <= 配列a × 配列b
$ans = mul($ans, $c); ## ans <= ans × 配列c

# 結果出力
print join(', ', @$ans), "\n";
% perl ./product.pl
A1-B1-C1, A1-B1-C2, A1-B1-C3, A1-B1-C4, A1-B2-C1, A1-B2-C2, A1-B2-C3, A1-B2-C4, 
A2-B1-C1, A2-B1-C2, A2-B1-C3, A2-B1-C4, A2-B2-C1, A2-B2-C2, A2-B2-C3, A2-B2-C4, 
A3-B1-C1, A3-B1-C2, A3-B1-C3, A3-B1-C4, A3-B2-C1, A3-B2-C2, A3-B2-C3, A3-B2-C4
$ans = mul($ans, $d); ## ans <= ans × 配列d

http://ja.wikipedia.org/wiki/%E7%9B%B4%E7%A9%8D%E9%9B%86%E5%90%8...

◎質問者からの返答

お見事です。エレガントなコードありがとうございました。

直積、というのですね。記憶の片隅にもなくお恥ずかしいかぎりです。


2 ● tera-p
●50ポイント

UNIX もしくは Cygwin 環境をお使いなら,Bash で一発展開できます.

$ echo {A1,A2,A3}-{B1,B2,B3}-{C1,C2,C3,C4} ← "$" より後を入力

A1-B1-C1 A1-B1-C2 A1-B1-C3 A1-B1-C4 A1-B2-C1 A1-B2-C2 A1-B2-C3 A1-B2-C4 A1-B3-C1 A1-B3-C2 A1-B3-C3 A1-B3-C4 A2-B1-C1 A2-B1-C2 A2-B1-C3 A2-B1-C4 A2-B2-C1 A2-B2-C2 A2-B2-C3 A2-B2-C4 A2-B3-C1 A2-B3-C2 A2-B3-C3 A2-B3-C4 A3-B1-C1 A3-B1-C2 A3-B1-C3 A3-B1-C4 A3-B2-C1 A3-B2-C2 A3-B2-C3 A3-B2-C4 A3-B3-C1 A3-B3-C2 A3-B3-C3 A3-B3-C4 ←ここまで出力

上記の入力を,

$ echo {A1,A2,A3}-{B1,B2,B3}-{C1,C2,C3,C4}-{D1,D2,D3}

としても動きます(出力は長くなるので割愛します).

◎質問者からの返答

ほんとだ! すごい!

なんで、こういう出力になるんでしょう?

いやーこれはすごい。

関連質問


●質問をもっと探す●



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