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

A 回答 (4件)

> 「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 からランダムに1つのカウンタを取り出します。(→@cnt)
 @cnt の中身を、ランダムに並べ替えます。(→@rand)
 @rand を使って、@array の中身を取り出します。(→@combi)
 @combi を表示します。

 この辺の流れを、必要数分ループさせます。
 また、ランダムに値を取り出す時は、重複しないようにフラグで管理します。(→@f1,@f2)
    • good
    • 0
この回答へのお礼

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

お礼日時:2001/08/09 18:27

多重ループにすると、nCrの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];   # 1つの組み合わせが完成
  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
 のように、リダイレクトすればOKです。

この回答への補足

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

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

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

補足日時:2001/08/09 09:04
    • good
    • 0

#1の補足です。

答えが不足してました。順列だけで終ってしまってました。

組み合わせについてはI<J<K<Lの条件を追加するだけでいいです。
もっと効率を上げるには、Iに対して、J=I+1からループ開始、、K=J+1から、L=K+1からそれぞれ始まるようにプログラムを組めば重複は排除され組み合わせが得られます。

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

この回答への補足

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

補足日時:2001/08/07 18:28
    • good
    • 0

Perlはよく知りませんので考え方のみを。


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

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

1番外のループではI=1,26でループを回します。
2番目(内側のループもJ=1,26でループを回します。このときI=Jなら何もせずにループエンドに行き、Jが一つ進みます。
次に3番目のループです。ここもK=1,26でループを回します。
この中ではI=K又はJ=KならKが一つ進むようにします。
この応用で4番目まで作ります。この中でI=L,J=L,K=LでなければI,J,K,Lが全て違うわけです。後はI,J,K,Lを文字に対応させます。

別の方法として一重ループでやる方法もあります。M=1から26^4までループさせます。そしてMを4桁の26進数に分解します。これをI,J,K,Lとすると後はおんなじですね。

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

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード


おすすめ情報