コンビネーション（例：5C3）の実現には…

質問

Perlのスクリプトを書いている中で、Out of Memoryに悪戦苦闘しているものです。
多次元配列同士を掛け合わせて、文字列を生成するプログラムを作成しています。

－以下スクリプト－

@list = (["りんご","みかん","レモン"],
　　　　　["ジュース","サイダー","リキュール","酒","スープ","アイス","キャラメル"],
　　　　　["クレープ","パイ","ケーキ","スイーツ","チャンプルー"],
　　　　　["～","…","・"],
　　　　　["1人前","200g","1000円分","山盛り","ちょっと","一皿"]);
$count=0;
for(@{$listy[0]}){
　　$seed[$count] = $_;
　　$count++;
}
$count=0;
for($i=1; $i<@listy; $i++){
　　for($j=0; $j<@{$listy[$i]}; $j++){
　　　　for($k=0; $k<@seed; $k++){
　　　　　　$tmp[$count] = $seed[$k] . $listy[$i][$j];
　　　　　　$count++;
　　　　}
　　}
@seed = @tmp;
$count = 0;
}

print join("\n",@tmp)."\n";

－ここまで－
動作結果：
りんごジュースクレープ～1人前
みかんジュースクレープ～1人前
…

こんな感じで、前から順番に総当りをしていくようにして文字列を生成する方法をとっているのですが、
これを配列の内、3つだけ取り出して文字列を繋げるようなスクリプトに変更するにはどうしたらよろしいでしょうか。

例1：りんごジュース山盛り
例2：ジュース…1人前

どなたかご助力頂ければ嬉しい限りです。宜しくお願い致します。m(_ _)m

回答No.3

kumoz

>>「配列 0 .. 4 から 3個の要素を取り出したすべての組み合わせを作りたい」
> まさにその通りです。配列数も可変で、なおかつn個の要素を取り出した全ての組み合わせ…ということです。

次のプログラムは、for ループで n 個の組み合わせを生成し、comb ですべての組み合わせを生成します。
@list と $n を変更すると、柔軟に対応できると思います。

use strict;
my @list = (["りんご","みかん","レモン"],
["ジュース","サイダー","リキュール","酒","スープ","アイス","キャラメル"],
["クレープ","パイ","ケーキ","スイーツ","チャンプルー"],
["～","…","・"],
["1人前","200g","1000円分","山盛り","ちょっと","一皿"]);

my $n = 3;
my @order = 0 .. ($n - 2);
my @limit = map { $_ + @list - $n } @order; $order[-1] -= 1;
for (my $i = $#order; $i >= 0; $i--) {
if ($order[$i] < $limit[$i]) {
$order[$i]++;
if ($i < $#order) {
$order[$_] = $order[$_ - 1] + 1 foreach $i + 1 .. $#order;
}
foreach my $j ($order[-1] + 1 .. $#list) {
comb(@order, $j);
}
$i = $#order; redo;
}
}

my @work;
sub comb {
my $idx = shift;
foreach my $item (@{$list[$idx]}) {
push @work, $item;
if (@_) { comb(@_); }
else { print join('', @work), "\n"; }
pop @work;
}
}

回答No.2

Tacosan

いろいろ考えられるんだけど, 「n進数の列挙」が安全かなぁ. つまり, d個の指数の組を用意しておいて,
・下位の指数を 1増やす
・オーバーフローしたら上の指数に伝播させる
という感じ.
これを無駄にリッチに作ってみる試み:
use strict;

sub newIndex {
my ($this, $d) = @_;
if (@{$this->{indices}}) {
[($this->{indices}[-1][0]+1) .. ($this->{elements} - $this->{depth} + $d)];
} else {
[0 .. ($this->{elements} - $this->{depth})];
}
}

sub newProducer {
my ($elements, $depth) = @_;

+ { elements => $elements, depth => $depth, indices => [], finished => 0 };
}

sub nextCombination {
my ($this) = @_;
return () if $this->{finished};

if (@{$this->{indices}}) {
my $d = $this->{depth};
shift @{$this->{indices}[-1]};
while (! @{$this->{indices}[-1]}) {
pop @{$this->{indices}};
unless (@{$this->{indices}}) {
$this->{finished} = 1;
return ();
}
shift @{$this->{indices}[-1]};
--$d;
}
while ($d < $this->{depth}) {
push @{$this->{indices}}, newIndex($this, $d++);
}
} else {
for my $d (0 .. ($this->{depth}-1)) {
push @{$this->{indices}}, newIndex($this, $d);
}
}

map { $_->[0] } @{$this->{indices}};
}

my $i = 0;
my $p = newProducer(5, 3);
while (my @comb = nextCombination($p)) {
print "$i: [", join(',', @comb), "]\n";
$i++;
}

回答No.1

Tacosan

Out Of Memory が出てくる必然性が分かりませんが.... 結果をすべて覚えておく必要ってあるんでしょうか.
さておき, この例だとやりたいことは「配列 0 .. 4 から 3個の要素を取り出したすべての組み合わせを作りたい」ということでいい? 「3個」があらかじめ分かっているなら 3重ループで作るだけなので難しい要素が見当たらない. 「3個」を可変にすると面倒になるけど, 実は本質的に「n進数の列挙」と同じです.
ところで, 結果として「みかん酒チャンプルー」とかいう訳の分からないものも許すのね?

補足

お返事ありがとうございます。
データベースから要素を読み込んで、多次元配列に格納し、
配列の内容が8個で、その下に10くらいの要素が存在する場合…などでOut Of Memory…となったりしていたので、
配列の内容によって、例えば用いる配列数が3なら、4以上の場合にコンビネーションを用いて配列を選択し、組み合わせを考えよう…というものでした。説明不足ですみません。

訳分からないものを許し、「3個」は定数ですが、プログラムの序盤で可変で行いたいと考えています。

>「配列 0 .. 4 から 3個の要素を取り出したすべての組み合わせを作りたい」
まさにその通りです。配列数も可変で、なおかつn個の要素を取り出した全ての組み合わせ…ということです。