OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
解決
済み

乱数と順列と組み合わせ

  • 困ってます
  • 質問No.114807
  • 閲覧数685
  • ありがとう数2
  • 気になる数0
  • 回答数4
  • コメント数0

お礼率 40% (2/5)

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

質問者が選んだベストアンサー

  • 回答No.4
レベル12

ベストアンサー率 75% (398/526)

> 「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)
お礼コメント
mick387

お礼率 40% (2/5)

たびたびすみません。動きました。どうもありがとうございました。
あとはもうちょっと意味を理解して、適宜アレンジして使いこなせるように頑張ります!!
投稿日時 - 2001-08-09 18:27:31
-PR-
-PR-

その他の回答 (全3件)

  • 回答No.1
レベル14

ベストアンサー率 30% (2593/8599)

Perlはよく知りませんので考え方のみを。 順列や組み合わせで乱数を使うと言うのは聞いたことが有りません。なぜなら、全てのケースがいつ終わるのかと言うことが明確に予測できないからです。 このような場合、普通は多重ループを使います。例えば英字26文字の中から4文字を選び、4文字の中に同じ文字がないものを探すとします。 1番外のループではI=1,26でループを回します。 2番目(内側のループも ...続きを読む
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とすると後はおんなじですね。

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


  • 回答No.2
レベル14

ベストアンサー率 30% (2593/8599)

#1の補足です。答えが不足してました。順列だけで終ってしまってました。 組み合わせについてはI<J<K<Lの条件を追加するだけでいいです。 もっと効率を上げるには、Iに対して、J=I+1からループ開始、、K=J+1から、L=K+1からそれぞれ始まるようにプログラムを組めば重複は排除され組み合わせが得られます。 早とちりでご迷惑かけました。 ...続きを読む
#1の補足です。答えが不足してました。順列だけで終ってしまってました。

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

早とちりでご迷惑かけました。
補足コメント
mick387

お礼率 40% (2/5)

概要はわかりました。どうもありがとうございます。
まだPerlの文法にもそれほど詳しくないので、言われたようにこなすのに四苦八苦しているところです。
なかなかうまく文字と数字が対応してくれなかったり、ほしいものだけを表示することができなかったり・・・
もう少し頑張ってみますが、もしPerlでの上手な表現方法がすぐにわかる方がいましたら参考までに教えていただけませんか?
(自分のはとても自己流なのでお世辞にも美しいプログラムとはいえないと思うので・・・)
投稿日時 - 2001-08-07 18:28:01
  • 回答No.3
レベル12

ベストアンサー率 75% (398/526)

多重ループにすると、nCrのrの数に応じてループが深くなり、かつ汎用的でないので、普通は再帰かそれと同等の動作をするループにします。 ちょっと作ってみましたが、ぱっと見ても恐らく分からないと思いますんで、いろいろ解析してみて補足してください。 # combi.pl # ---- declare my (@combi, @cnt, $f_loop); my @array = (0, 1 ...続きを読む
多重ループにすると、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です。
補足コメント
mick387

お礼率 40% (2/5)

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

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

というのは可能でしょうか?
どこかに「配列をランダムに並びかえる」スクリプトを潜り込ませようとしたのですがうまくいきませんでした・・・
投稿日時 - 2001-08-09 09:04:24
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
こんな書き方もあるよ!この情報は知ってる?あなたの知識を教えて!
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ