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


配列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"] を返す。

回答の条件
  • 1人3回まで
  • 登録:2008/03/30 01:12:27
  • 終了:2008/04/01 00:23:59

ベストアンサー

id:khoshi3 No.1

khoshi3回答回数71ベストアンサー獲得回数122008/03/30 02:15:52

ポイント40pt

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

  • サンプルソースコード(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
  • 4つ以上の配列を直積するには、以下の行を追加するか、for文でループさせるかして下さい。:
$ans = mul($ans, $d); ## ans <= ans × 配列d
  • 直積集合 - Wikipedia:

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

id:biz_tanaka

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

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

2008/03/30 03:53:16

その他の回答(1件)

id:khoshi3 No.1

khoshi3回答回数71ベストアンサー獲得回数122008/03/30 02:15:52ここでベストアンサー

ポイント40pt

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

  • サンプルソースコード(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
  • 4つ以上の配列を直積するには、以下の行を追加するか、for文でループさせるかして下さい。:
$ans = mul($ans, $d); ## ans <= ans × 配列d
  • 直積集合 - Wikipedia:

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

id:biz_tanaka

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

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

2008/03/30 03:53:16
id:tera-p No.2

tera-p回答回数92ベストアンサー獲得回数212008/03/30 20:14:00

ポイント50pt

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}

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

id:biz_tanaka

ほんとだ! すごい!

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

いやーこれはすごい。

2008/03/30 23:08:04
  • id:tera-p
    > なんで、こういう出力になるんでしょう?

    回答そのものではないのでコメントで.

    もともとは,

    $ rm {foo,bar}.txt ← rm foo.txt bar.txt と同じ

    のように使われる機能です(glob 展開と呼ばれる機能の一部です).

    bash などでは上記の glob 展開は再帰的に適用されるので,

    {A1,A2}-{B1,B2}-{C1,C2} (例題をちょっと端折りました)は,

    A1-{B1,B2}-{C1,C2} A2-{B1,B2}-{C1,C2} に展開され,さらに,

    A1-B1-{C1,C2} A1-B2-{C1,C2} A2-B1-{C1,C2} A2-B2-{C1,C2} に展開されて…というように{}がなくなるまで展開されていきます.

    #私も,この振る舞いを初めて知ったときには「おおー」と思いました.
  • id:biz_tanaka
    biz_tanaka 2008/04/01 00:22:54
    なるほどー。
    勉強になりました。これ考えた人えらいですね。
    先人は偉大だ。

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

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

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

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