- ベストアンサー
重複しない乱数の生成
他の質問での回答に対してもう少し具体的に知りたいと思って投稿しました。 自分はいわゆる日曜プログラマです。 勉強のつもりでOKWebのコンピュータ関連でいろいろ回答してます。 (未熟者なのでとんちんかんなのが多いですが) で次の質問に回答しました。内容は「重複しない乱数を発生させる方法」です。 http://okweb.jp/kotaeru.php3?q=1239644 私が回答したのは#10です。私の考えは 1. 最初に配列に重複しない値を入れ(1から100を順番に) 2. 2要素の値を入れ換える 3. 2を任意の回数繰り返す 4. 配列の先頭から値を取り出す という考えです。 が、そのあと#12の回答があり、それを読むと私の方法ではマズイようです。 「どうしてマズイのか」ということはなんとなくわかった(ような)気がするんですが、 では「具体的にどうすべきなのか」が知りたいです。 違う方法として自分ではこう考えました。 上記1の配列(これを配列Aとする)と同じ要素数(ここでは100個)の配列Bを作って 1. 0～(配列Aの要素数 - 1)の範囲で乱数を発生させる -> 得られた数値をnとする 2. 配列A[n]の値を配列Bに入れる -> 最初は配列B[0]に入れる 3. 配列A[n]を削除 -> 要素数が1個減る 以下これを繰り返し、配列B[99]まで入れて終了。 過去の質問を覗いてみましたが、いろいろな方法があってどれがいいのか迷ってきま した。どちらかというと具体的なソースではなく考え方を教えてください。 よろしくお願いします。
- その他（プログラミング・開発）
- 回答数11
- ありがとう数12
- みんなの回答 （11）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (10)
- bender
- ベストアンサー率45% (108/236)
#3 です。 質問文を読み返すと、質問された方が書かれているアイディアは、#1の方と、考え方としては同じであることに気づき、私の説明は蛇足であったと思いました。問題文を注意深く読まず失礼しました。 #7 の方が計算されているのですが、「入れ替え法」は、Ｎ個の要素があるとき、Ｎ！の状態（並び方）を遷移する Markov Chain という確率過程ではないでしょうか（参考ＵＲＬ）。各状態からの遷移確率が「同じように」なっているので、収束する際には、ある状態（並び方）にある確率が同じになるはずでは、と考えました。 既出ですが、「入れ替え法」では最低Ｎ－１回の入れ替えをしないことにはたどり着けない並び方があるように思います（要素が一個づつずれたような並び方）。
お礼
参考URLありがとうございました。 正直、数学の知識がない上に、英語のページなので私には難しすぎるのです が、できることからぼちぼち勉強します。道は険しいですが...。
- shkwta
- ベストアンサー率52% (966/1825)
#7です。 勘違いして申し訳ありません。入れ替え法の場合、交換の相手が自分自身であることを許容すると交換が奇数回か偶数回に関係なく等確率に収束します。 計算例を示します。 (1,2,3)から出発して (3,1,2)ができる各回の確率 0, 0.88888/6, 0.88888/6, 0.98765/6, 0.98765/6, 0.99863/6, 0.99863/6, ・・・ このあとは、2回ごとに 1/6 との誤差が 1/9倍になります。 (1,2,3,4)から出発して (4,1,2,3)ができる確率 0, 0, 0.75/24, 0.75/24, 0.9375/24, 0.9375/24, 0.984375/24, 0.984375/24, ・・・ このあとは、2回ごとに 1/24 との誤差が 1/4倍になります。 どうやら、確率の不均等は指数関数的に減少するようですが、証明があるかどうかはわかりません。
お礼
学校で数学を勉強したのはもう20年以上前なので、正直、確率とかの話にな ると「遠い昔の思い出」って感じです。 いくつになっても勉強だなー、と痛感いたします。
- UKY
- ベストアンサー率50% (604/1207)
誤解があるといけないので、補足。 shkwta さんのおっしゃる偶置換・奇置換の話は、私や BLUEPIXY さんが考えている入れ替えとは前提条件が違います。 私や BLUEPIXY の話に出てくる入れ替えには「同じ数同士を入れ替える」つまり「実質的には入れ替えないのと同じ」パターンが含まれているのに対し、shkwta さんの話ではこのパターンを含みません。 例えば、同じ数同士を入れ替えるパターンを含む入れ替えを考える場合に、偶置換・奇置換の違いを考えるのは意味がないということです。(前提条件がごっちゃになっている) 以上、文面から誤解する人がいるかもしれないと思ったのでちょっと補足しました。
お礼
たびたびありがとうございます。なにしろ自分で判断できるほどの理解力が ないので、丁寧に説明していただくのはとてもうれしいです。 貴重なお時間を割いていただいてありがとうございました。
- shkwta
- ベストアンサー率52% (966/1825)
入れ替え法について補足します。 有限回の入れ替えでは、すべての順列が厳密には等確率にはなりませんが、回数を多くすると限りなく等確率に近づきます。しかし、各入れ替えごとに、順列のうち半分しか実現しないことに注意が必要です。 たとえば、(1,2,3)の入れ換えですと、奇数回の入れ替えでは(1,3,2) (2,1,3) (3,2,1)の３つだけが実現し、偶数回の入れ替えでは(2,3,1) (3,1,2) (1,2,3) の３つだけが実現します。前者を奇置換、後者を偶置換といいます。 したがって、入れ換え回数を偶数にするか奇数にするかというところも乱数で決めないと、全部の順列に行き渡らないことになります。 No.4の方の質問ですが、(1,2,3)を２回入れ替える方法は9通りあります。9通りの中に(2,3,1) (3,1,2) (1,2,3) の３つの偶置換が３つずつ入っています。この場合はたまたま等確率ですが、(1,2,3,4)と要素を4つにすると入れ替えでは等確率にはなりません。
お礼
奇置換、偶置換という言葉を初めて知りました。勉強になります。 いろいろ方法があるもんですね。一人で考えてると方法が偏ってしまって。 ありがとうございました。
- UKY
- ベストアンサー率50% (604/1207)
「ランダムに選んだ二つの数を入れ替える」を何度も繰り返す方法 (前の質問の masa_pee さんの方法) がいけないのは、100% ランダムなシャッフルができない、という点です。 値の入れ替えを何度繰り返せば 100% ランダムにシャッフルできたと言えるでしょうか? 2回や3回ではもちろん駄目ですよね。選ばれない数 (入れ替えをしない数) がまだたくさんあります。 100 個の数の配列に対し 100 回入れ替えを行っても、まだちょっと不安ですよね。乱数の偏りによって、選ばれない数がいくつかあるかもしれない。では 300 回ならどうか? ほとんど問題ないと思いますが、数学的にはまだ完全に 100% だとは言えません。 100% ランダムにシャッフルするには、無限回の入れ替えをする必要があるのです。 ポイントは、乱数の偏りによって選ばれない数があるかもしれない、という点です。100% ランダムにシャッフルするには、全ての数を同じ割合で選んでゆく必要があります。 そして、masa_pee さんが今回の質問文に書いた方法や、cyoki_par さんの回答文にある方法が、まさにその 100% ランダムにシャッフルできる方法なのです。 前の質問で BLUEPIXY さんがおっしゃっている「交換の結果は均等な結果にならない」ことですが、三つの数のうち二つをランダムに一回入れ替えるという例で考えてみます。 三つの数をランダムに並べた結果は 6 通りあります。 [123][132][213][231][312][321] これら 6 通りから、それぞれ 1/6 の確率でどれか一つを選ぶのが、100%ランダムなシャッフルですね。 しかし、[123]という配列をあらかじめ用意しておいて、ランダムに選んだ二つの数を 1 回入れ替える、という操作を行ったとき、結果は等確率にはならないのです。 ランダムに選んだ二つの数が同じだった場合――実質的には入れ替えないのと同じ――の確率は 1/3 になります。しかし、本当にランダムなシャッフルなら確率は (上に書いたように) 1/6 になるはずです。 つまり、この方法では [123] は他のものよりも出やすいのです。逆に、[312] あるいは [231] になる確率は 0 です。 もちろん、何度も何度も入れ替えれば確率は均等になってゆきますが、(無限回入れ替えない限り) きっかり 1/6 にはなりません。等確率ではない入れ替えを何度行っても、結果はやはり等確率にはならないのです。
お礼
#6 回答ありがとうございます。 > 値の入れ替えを何度繰り返せば ... 今回の件に限らず、「とりあえずできる」けど「本当にそれでいいのか」でよく悩みます。 こういうときに気軽に訊ける人がいればいいんですがね。
補足
お礼を下書きから写したときに余分なものが入ってしまいました。 > #6 なんかこれじゃ#6さんを呼び捨てにしてるみたいで。単なる間違いですので。
- ymmasayan
- ベストアンサー率30% (2593/8599)
重複しない乱数を発生させる方法としては、No.2の方の方法が一番オーソドックスです。 無駄な試行も無いですしロジックも比較的簡単です。 私もよく使っています。 前回の質問のNo.12の方の指摘は無視して結構です。 ９通りのうち、自分自身を入れ替える３通りを除けばちゃんと６通りになりますし、 乱数としておかしくなる要素は全く有りません。 ただ、害は無いですが、自分自身を入れ替えるのは無駄ですね。 それと最後に余分な話ですが、重複の無い乱数と言うのは本当の乱数ではありません。 本当の乱数なら同じ数字が続く事もあるのです。 重複がないと言うことは単なる「シャッフル」ということで擬似乱数ですね。
お礼
最後の「余分な話」ですが、余分ではなく、大変ためになります。 経験者の方の御意見はたいへん参考になります。 ありがとうございました。
- hide9048
- ベストアンサー率42% (6/14)
質問読みましたが、No.1およびNo.3に同意です。 元の質問のリンク先にある「9通り」「6通り」の意味がどうもよく分かりません。 あと「乱数」と「順番入れ替え」を整理して考える必要があると思います。 そもそも交換による「順番入れ替え」法は、トランプなどの「シャッフル」をプログラム上で実現させるためのアルゴリズムであって、乱数を発生させる方法ではないです。 「シャッフル」はカードを配り終えたときに、すべてのカードが均等に1回ずつ出現することが保証されなければなりませんが、「乱数」ではそのような保証はありません。というか、保証がある時点で「乱れた」数ではなくなってしまいます。
お礼
回答ありがとうございます。 > あと「乱数」と「順番入れ替え」を整理して考える必要があると思います。 うーん、こういうところのあいまいさが間違いの原因なんでしょうね。
- bender
- ベストアンサー率45% (108/236)
私もＮｏ．１（Ｎｏ．２）の方が書かれた方法がよいのでは、と考えています。というのも、これは例えば、０から９９までの数字がそれぞれ書いてある１００個のボールを、袋から「ランダム」に一つずつ（取ったボールは袋に戻さずに）１００回取り出すことと同じ効果があると思えるからです。 ところで便乗質問なのですが、質問された方が以前投稿された回答（Ｎｏ．１０）で、任意の２数を交換する手続きの回数が「十分大きい」場合、はじめの数字の並べ方の順番の影響が少なくなり、結果として得られる数列を「ランダム」といってもさしつかえなくなるのではないでしょうか？ また、Ｎｏ．１２の方が書かれている「９通り...６通り...」ということが、「ランダム」でない説明としてどのように関係しているのかわからないので、補足してくださる方がいれば幸いです。 いずれにしても、以下のＮｏ．１の方が書かれた方法だと、手続きが（「十分に大きな回数」ではなく）１００回で終わるので、やはりこの方法が効率的でよいかと私は思います。
お礼
ありがとうございます。 OKWebを読んでると「こうすればできるよ」という回答はよく目に付くんですが、 あと一歩「どうしてこうするのか」が知りたいことがあるんですよね。
- cyoki_par
- ベストアンサー率28% (9/32)
- cyoki_par
- ベストアンサー率28% (9/32)
１．Ａ（０）からＡ（９９）までの配列を用意して、０から９９までの値を入れておく。 ２．０から９９までの乱数を発生させる。 ３.Ａ（９９）にその乱数を書き、その乱数の配列に９９を書く。 ４．０から９８（ここがポイント）までの乱数を発生させる。 後は同じことを繰り返せばよいです。 最近のプログラマーは、このようなテクニックをあまり知らないようです。 言語の使い方ばかりは得意なようですが。
お礼
なるほど。シンプルなことなんですね。ありがとうございました。
関連するQ&A
- 重複なし乱数について
重複なし乱数について VBAで重複なしの乱数を使ったプログラムを作りたいのですが上手く作れません。 助言お願い致します。 作るのは数比べゲームです。 フォーム上にボタン0～9を配置し、ボタンを押すごとに重複しない乱数をPC側で表示させ、 選択した数字と乱数を比較し勝敗を決定するというゲームです。 エクセル上に重複なし乱数を表示する方法はなんとなく分かるのですが、 ボタンを押すごとに重複なし乱数を取得する処理を行う方法が分かりません。 現状としては ボタンを押した処理の欄に pcNo = Int(9 * rnd + 0) を書いてただ乱数を取得している状態です。 回答よろしくお願い致します。
- ベストアンサー
- Visual Basic
- javaの乱数生成プログラム-バグを教えてください
こんにちは。Web上で「重複しない乱数」を作るプログラムをいくつか見まして、どれもこれも何でこんな複雑なステップを踏むのであろう思い、どーだこんなに簡単に作れるじゃん・・・と0-9までの整数で乱数を生成するプログラムを書いてみたんです。これならAPI調べなくたって基本を身につけていれば誰でも書けると・・・けど、生成する乱数の数が100個とか200個とかなら問題ないんですが、例えば9桁の乱数を10000個作るように設定しても7500個くらいしかListに入りません。原因がどこにあるかお教えいただけますでしょうか。なにとぞよろしくお願いします。 import java.util.ArrayList; import java.util.List; public class RandomExec { static int idLength=9; //乱数の桁数を指定 static int elmSize=100; //生成する乱数の個数を指定 static List<String> list = new ArrayList<String>(); //乱数を格納するリスト public static void main(String[] args) { addList(); //生成された乱数を要素に持つリスト list を取得 //要素をひとつずつコンソール出力 for(String s : list){ System.out.println(s); } } //リストに入れるための乱数を生成するメソッド public static String addId(){ int[] id=new int[idLength]; //int配列idを宣言(要素数=乱数の桁数) String s=""; String str; //配列にMath.random()で取得した要素を入れる for(int i=0; i<idLength; i++){ int n=(int)(Math.random()*10); id[i]=n; } //指定した桁数(この場合は9個)の数字から成るString s を得るため //int型配列idの要素をStringに変換し、すべての要素を連結する for(int n : id){ str = String.valueOf(n); s+=str; } return s; //生成されたStringを返す(下のaddList()メソッドに返しています) } //addIdメソッドで作った要素候補をチェックし、重複がなければListに加えるメソッド //List list の要素数が変数elmSizeで指定した乱数の数と同じになるまで繰り返す public static void addList(){ while(list.size()<elmSize){ //addIdメソッドでｌistの要素候補strを取得 String str = addId(); //listに候補と同じ文字列を持つ要素が存在しなければlistに加える if(!list.contains(str)) list.add(str); } } }
- ベストアンサー
- Java
- 要素数が10の配列で、乱数0～9の値が重複しないようにする方法がわからなくて困っています。
JAVAの練習問題でわからなくて困っています 以下は線形探索のプログラムで、このプログラムを改良して、 要素数が10の配列で、乱数0～9の値が重複しないようにする方法がわからなくて困っています。 以下のような簡単なプログラムでできる方法で行いたいです。 どなたか答えまたはヒントを下さい、お願いします。 ------------------------------------------------------------ import java.util.Random; import java.util.Scanner; public static void main (String[] args) { Random rand = new Random(); Scanner stdIn = new Scanner(System.in); final int n = 10; //要素数 int[] a = new int[n]; //配列を宣言 for (int j = 0; j < n;) a[j] = rand.nextInt(10); System.out.print("配列aの全要素の値\n{ "); for (int j = 0; j < n; j++) System.out.print(a[j] + " "); System.out.println("}"); System.out.print("探す数値 : "); int key = stdIn.nextInt(); int i; for (i = 0; i < n; i++) if (a[i] == key) break; if (i < n) //探索成功 System.out.println("それはa[" + i + "]にあります。"); else //探索失敗 System.out.println("それはありません。"); } }
- 締切済み
- Java
- 重複しない乱数を作り配列に入れる（AS3.0）
Flash Pro CS5 AS3.0 で記述しています。 １～１０の整数をランダムかつ重複せずに配列に格納したいと考えています。 そこで，ネット上で参考になるソースを見つけ， 以下のように書き直しました。 var int_a = new Array(); var int_b = new Array(); function RandomInt():void{ //ここだけ変更すればよい var maxN:Number = 10;//乱数の最大値 //0～maxNの数字を全部配列に入れる for (var i:int=0; i< maxN; i++) { int_a[i] = i+1; } var j:Number = 0; var a_length:Number = int_a.length; //要は配列をシャッフルする while (a_length) { var int_r:Number = Math.floor(Math.random()*(maxN+1-j)); //乱発生した整数を配列int_bに順番に入れ、int_aから削除する int_b[j] = int_a.splice(int_r, 1); j++; //配列int_a内の数字が一つずつ減っていく a_length = int_a.length; } //ここで配列int_bがシャッフルされた trace(int_b); } RandomInt(); としました。 しかし出力結果がなぜか 8,2,4,9,,7,6,5,10,3,1のように抜けている部分があり， 次のフレームで for(var j:int=1; j <= 10; j++){ trace(int_b[j]); } として確認してもやはり 2 4 9 7 6 5 10 3 1 となってしまします。 どの部分がおかしいのか教えていただきたいです。 また，乱数発生の部分で Math.floor(Math.random()*(maxN+1-j)); という風に記述してあったのですが，ここは間違いではないのでしょうか？ jを引いていくと発生する乱数の範囲が徐々に狭くなっていってしまうと思ったのですが； それとも元のソースコードを使って ttp://www.renowan.com/blog/?p=143 ０～９までの乱数を発生させてそれぞれに１を足す方が簡単でしょうか？ よろしくお願いします。
- ベストアンサー
- Flash
- 乱数の出し方で・・・
たとえば、３９人を乱数を使って並べ替えたいのですが、Ｂ列以降に名前や必要な項目を書き、Ａ列に=RAND()を入れそれを使って並び替えるのではなく、１から３９までの乱数を重複なしに発生させることはできないのですか？？？
- ベストアンサー
- オフィス系ソフト
- java 乱数を並べて重複させない方法
javaのプログラミングについて質問させてください。 まだ勉強し始めの初級者です。 1~25までの乱数を発生させ それらを重複させずに５列×５行に並べたいのですが、 Randomとfor文を使い乱数を発生させる事はできたのですが重複してしまいます。 ネットで調べたらArraylistのcontainsを使う等書いてあったのですが方法が分かりません。 ５列×５行というのは ○、○、○、○、○、 ○、○、○、○、○、 ○、○、○、○、○、 ○、○、○、○、○、 ○、○、○、○、○、 という風に並べたいです。（○はすべて違う数字） どなたか分かる方ご教授よろしくお願いします。
- ベストアンサー
- Java
- 乱数ってなんですか？
なんどもすいません。配列のはなしなんですが、まずＡという配列の中の０～１０番目の中身をランダムに動かして、Ｂという配列に再編成させたいのですが、 乱数を使えば簡単になるよと知り合いにはいわれたのですが、乱数がどうゆうもの だかあまりよくわかりません。 自分は今ＶＣ＋＋のＭＦＣで作ってるのですが、乱数自体がわからないので教えてください。 それとこの方法でいくと日本語の時は配列を２個づつランダムに変えることになると思うのですが、それはぜんぜん予想もできません。教えていただけると助かります。お願いします。
- ベストアンサー
- C・C++・C#
お礼
お礼が遅くなってすみません。 BLUEPIXYさんはこの質問のきっかけになった方なので、御本人から回答いた だけてたいへん嬉しいです。ありがとうございました。 おかげで疑問がとけました。
補足
PLUEPIXYさんの回答はいつも「的確だなー。すごいなー」と思って読ませて いただいてます。今回は私の誤りに気づかせていただいてたいへん感謝して おります。 実は向こうの質問でお聞きしようとも思ったのですが、質問者ではないのに あまりかき回すのはよくないかなと思い、質問を立ち上げた次第です。 もし、BLUEPIXYさんに余計なお手間を取らせたとしたら申し訳ございません。 ひとえに私の理解力のなさが原因です。お許しください。