乱数と順列と組み合わせ

質問

初心者です。MacPerlを使っています。
Perlを使って、例えば9個の文字の中から4個を選ぶ、という組み合わせを、すべてのパターンについてもれなく行うことはできますか？
完全にランダムなものはできました。（例えば、3個の文字を使って4文字からなる配列をすべて（3^4=81通り）作る、など。ひたすら作って同じ配列を消す、というあまり美しくない方法ですが・・・）
ですが、rand関数を使うと、同じものが出てきてしまうことがあるので、数学でいうところのcombinationをつくることができずにいます。
permutationはなんとかできたのですが。。（これもやはり、同じものを消せばいいので。）
combinationの場合、「並び方」は問わないので、同じ要素からなるが順列が異なる配列を同じものとして消したいのです。
どなたかその方法がわかる方はいらっしゃいますか？

回答No.4

leaz024 · ベストアンサー

> 「n個の中からr個を選んで＜ランダムに＞並べる」
なるほど、それで乱数なんですね。

No.3のコードを改造してみました。ご参考までに。

# combi.pl

# ---- declare
my (@allcnt, @cnt, $f_loop);
my @array = (0, 1, 3, 4, 6, 8, 9);
my $r = 5;

# ---- init
srand(time);

# ---- make counter list
@cnt = (0 .. $r-1);
$f_loop = 1;
while ($f_loop) {
　　push @allcnt, [@cnt];

　　$f_loop = 0;
　　for (my $i = $r-1; $i >=0; $i--) {
　　　　if ($cnt[$i]-$i < @array-$r) {
　　　　　　$cnt[$i]++;
　　　　　　while (++$i < $r) { $cnt[$i] = $cnt[$i-1] + 1; }
　　　　　　$f_loop = 1;
　　　　　　last;
　　　　}
　　}
}

# ---- main
my (@combi, @f1, $s);
foreach (0 .. $#allcnt) {
　　do { $s = int(rand() * @allcnt) } while ($f1[$s]);
　　$f1[$s] = 1;
　　@cnt = @{$allcnt[$s]};

　　my (@rand, @f2, $t);
　　foreach my $j (0 .. $r-1) {
　　　　do { $t = int(rand() * $r); } while ($f2[$t]);
　　　　$f2[$t] = 1;
　　　　$rand[$t] = $cnt[$j];
　　}

　　@combi = @array[@rand];
　　print "@combi\n";
}
__END__

■簡単に解説を。
# ---- make counter list
　$r 個分のカウンタ（@cnt）を、全組み合わせの数分求めます。（→@allcnt）
# ---- main
　@allcnt からランダムに１つのカウンタを取り出します。（→@cnt）
　@cnt の中身を、ランダムに並べ替えます。（→@rand）
　@rand を使って、@array の中身を取り出します。（→@combi）
　@combi を表示します。

　この辺の流れを、必要数分ループさせます。
　また、ランダムに値を取り出す時は、重複しないようにフラグで管理します。（→@f1，@f2）

お礼

たびたびすみません。動きました。どうもありがとうございました。
あとはもうちょっと意味を理解して、適宜アレンジして使いこなせるように頑張ります！！

回答No.3

leaz024

多重ループにすると、nＣrのrの数に応じてループが深くなり、かつ汎用的でないので、普通は再帰かそれと同等の動作をするループにします。

ちょっと作ってみましたが、ぱっと見ても恐らく分からないと思いますんで、いろいろ解析してみて補足してください。

# combi.pl

# ---- declare
my (@combi, @cnt, $f_loop);
my @array = (0, 1, 3, 4, 6, 8, 9);
my $r = 5;

# ---- main
@cnt = (0 .. $r-1);
$f_loop = 1;
while ($f_loop) {
　　@combi = @array[@cnt];　　　# １つの組み合わせが完成
　　print "@combi\n";　　　　　　 # 表示

　　$f_loop = 0;
　　for (my $i = $r-1; $i >=0; $i--) {
　　　　if ($cnt[$i]-$i < @array-$r) {
　　　　　　$cnt[$i]++;
　　　　　　while (++$i < $r) { $cnt[$i] = $cnt[$i-1] + 1; }
　　　　　　$f_loop = 1;
　　　　　　last;
　　　　}
　　}
}
__END__

■説明
　@array に、n個の値を設定してください。
　$r に、選ぶ個数を設定してください。
　結果の数が多い場合、
　　　perl combi.pl > result.txt
　のように、リダイレクトすればＯＫです。

補足

ありがとうございました。とりあえず、動かすことはできました。これから内容を理解すべく解析してみます。
ところで、前の方のアドバイスにそって自分で強引につくることもできたのですが、（これもまだどこが正しいのかわからないまま動いた）
どうしても、結果として出てくる配列の並び方は最初に決めた配列(@array)の並び方に依存していて、「ランダムに」並べることができません。

「n個の中からr個を選んで＜ランダムに＞並べる」

というのは可能でしょうか？
どこかに「配列をランダムに並びかえる」スクリプトを潜り込ませようとしたのですがうまくいきませんでした・・・

回答No.2

ymmasayan

＃１の補足です。答えが不足してました。順列だけで終ってしまってました。

組み合わせについてはＩ＜Ｊ＜Ｋ＜Ｌの条件を追加するだけでいいです。
もっと効率を上げるには、Ｉに対して、Ｊ＝Ｉ＋１からループ開始、、Ｋ＝Ｊ＋１から、Ｌ＝Ｋ＋１からそれぞれ始まるようにプログラムを組めば重複は排除され組み合わせが得られます。

早とちりでご迷惑かけました。

補足

概要はわかりました。どうもありがとうございます。
まだPerlの文法にもそれほど詳しくないので、言われたようにこなすのに四苦八苦しているところです。
なかなかうまく文字と数字が対応してくれなかったり、ほしいものだけを表示することができなかったり・・・
もう少し頑張ってみますが、もしPerlでの上手な表現方法がすぐにわかる方がいましたら参考までに教えていただけませんか？
（自分のはとても自己流なのでお世辞にも美しいプログラムとはいえないと思うので・・・）

回答No.1

ymmasayan

Perlはよく知りませんので考え方のみを。
順列や組み合わせで乱数を使うと言うのは聞いたことが有りません。なぜなら、全てのケースがいつ終わるのかと言うことが明確に予測できないからです。

このような場合、普通は多重ループを使います。例えば英字２６文字の中から４文字を選び、４文字の中に同じ文字がないものを探すとします。

１番外のループではＩ＝１，２６でループを回します。
２番目（内側のループもＪ＝１，２６でループを回します。このときＩ＝Ｊなら何もせずにループエンドに行き、Ｊが一つ進みます。
次に３番目のループです。ここもＫ＝１，２６でループを回します。
この中ではＩ＝Ｋ又はＪ＝ＫならＫが一つ進むようにします。
この応用で４番目まで作ります。この中でＩ＝Ｌ，Ｊ＝Ｌ，Ｋ＝ＬでなければＩ，Ｊ，Ｋ，Ｌが全て違うわけです。後はＩ，Ｊ，Ｋ，Ｌを文字に対応させます。

別の方法として一重ループでやる方法もあります。Ｍ＝１から２６＾４までループさせます。そしてＭを４桁の２６進数に分解します。これをＩ，Ｊ，Ｋ，Ｌとすると後はおんなじですね。

頑張ってください。わかりにくければ補足してください。