こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

重複しない乱数の生成

他の質問での回答に対してもう少し具体的に知りたいと思って投稿しました。

自分はいわゆる日曜プログラマです。
勉強のつもりで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]まで入れて終了。

過去の質問を覗いてみましたが、いろいろな方法があってどれがいいのか迷ってきま
した。どちらかというと具体的なソースではなく考え方を教えてください。

よろしくお願いします。

投稿日時 - 2005-02-27 05:53:15

QNo.1240730

暇なときに回答ください

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

>元の質問のリンク先にある「9通り」「6通り」の意味がどうもよく分かりません。
すでに、ちゃんとした回答がなされているので、特に言うことはないのですが、もとの質問での私の回答で、「均等な乱数が得られない。」というのが、ちょっと語弊があったと思います。すみません。
ここで、他の方の回答にもあるように、交換した結果のパターンの出現確率が一様にならないという意味です。
9通り、6通りというのは、
ある手順で起こりうる全事象の数が9であり
結果として起こりうる全事象の数が6である
ということで、
少なくとも、ある手順の結果起こりうる事象の数はこの場合6の倍数になっていなくてはなりません。
本当にどのような並びになっているかどうか調べるまでもなく、均等な出現にならないと判断できるということです。
つまり、9通り×9通り×…という手順を繰り返す方法では、6の倍数にならないので、結果としてできる出現パターンは均等になりません。
あと、
ABCを交換の結果ABCになったからといって、交換がなかったのと同じであるから無視して良いとはならないと思います。
もうすでに他の方が書かれているので、繰りかえしは避けますが、3つの様な、少ない要素数の場合は、交換の結果の(一回の手順での)出現パターンは、全部列挙して調べることができます。
ABCから任意の2つを交換して得られるパターン
ABC:3回
ACB:2回
BAC:2回
BCA:0回
CAB:2回
CBA:0回
全9通り
理想の場合は、これが各1回になって欲しいワケです。
このように、要素が少ない時、手順の回数が少ない時は、容易に調べられますが、そうでない時には、簡単には調べられません。
なので、9通り、6通りというのは、簡易に判別できる考えだと思います。

投稿日時 - 2005-02-27 14:34:46

補足

PLUEPIXYさんの回答はいつも「的確だなー。すごいなー」と思って読ませて
いただいてます。今回は私の誤りに気づかせていただいてたいへん感謝して
おります。
実は向こうの質問でお聞きしようとも思ったのですが、質問者ではないのに
あまりかき回すのはよくないかなと思い、質問を立ち上げた次第です。
もし、BLUEPIXYさんに余計なお手間を取らせたとしたら申し訳ございません。
ひとえに私の理解力のなさが原因です。お許しください。

投稿日時 - 2005-03-01 03:27:42

お礼

お礼が遅くなってすみません。
BLUEPIXYさんはこの質問のきっかけになった方なので、御本人から回答いた
だけてたいへん嬉しいです。ありがとうございました。
おかげで疑問がとけました。

投稿日時 - 2005-03-01 03:26:36

このQ&Aは役に立ちましたか?

2人が「このQ&Aが役に立った」と投票しています

回答(11)

ANo.11

#3 です。
質問文を読み返すと、質問された方が書かれているアイディアは、#1の方と、考え方としては同じであることに気づき、私の説明は蛇足であったと思いました。問題文を注意深く読まず失礼しました。

#7 の方が計算されているのですが、「入れ替え法」は、N個の要素があるとき、N!の状態(並び方)を遷移する Markov Chain という確率過程ではないでしょうか(参考URL)。各状態からの遷移確率が「同じように」なっているので、収束する際には、ある状態(並び方)にある確率が同じになるはずでは、と考えました。

既出ですが、「入れ替え法」では最低N-1回の入れ替えをしないことにはたどり着けない並び方があるように思います(要素が一個づつずれたような並び方)。

参考URL:http://www.staff.city.ac.uk/r.j.gerrard/courses/2dsm/dsm03_4.htm

投稿日時 - 2005-03-01 00:24:26

お礼

参考URLありがとうございました。
正直、数学の知識がない上に、英語のページなので私には難しすぎるのです
が、できることからぼちぼち勉強します。道は険しいですが...。

投稿日時 - 2005-03-01 03:46:38

ANo.10

#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倍になります。

どうやら、確率の不均等は指数関数的に減少するようですが、証明があるかどうかはわかりません。

投稿日時 - 2005-02-27 23:42:19

お礼

学校で数学を勉強したのはもう20年以上前なので、正直、確率とかの話にな
ると「遠い昔の思い出」って感じです。
いくつになっても勉強だなー、と痛感いたします。

投稿日時 - 2005-03-01 03:36:30

ANo.9

UKY

誤解があるといけないので、補足。

shkwta さんのおっしゃる偶置換・奇置換の話は、私や BLUEPIXY さんが考えている入れ替えとは前提条件が違います。
私や BLUEPIXY の話に出てくる入れ替えには「同じ数同士を入れ替える」つまり「実質的には入れ替えないのと同じ」パターンが含まれているのに対し、shkwta さんの話ではこのパターンを含みません。

例えば、同じ数同士を入れ替えるパターンを含む入れ替えを考える場合に、偶置換・奇置換の違いを考えるのは意味がないということです。(前提条件がごっちゃになっている)

以上、文面から誤解する人がいるかもしれないと思ったのでちょっと補足しました。

投稿日時 - 2005-02-27 15:10:14

お礼

たびたびありがとうございます。なにしろ自分で判断できるほどの理解力が
ないので、丁寧に説明していただくのはとてもうれしいです。
貴重なお時間を割いていただいてありがとうございました。

投稿日時 - 2005-03-01 03:33:22

ANo.7

入れ替え法について補足します。

有限回の入れ替えでは、すべての順列が厳密には等確率にはなりませんが、回数を多くすると限りなく等確率に近づきます。しかし、各入れ替えごとに、順列のうち半分しか実現しないことに注意が必要です。

たとえば、(1,2,3)の入れ換えですと、奇数回の入れ替えでは(1,3,2) (2,1,3) (3,2,1)の3つだけが実現し、偶数回の入れ替えでは(2,3,1) (3,1,2) (1,2,3) の3つだけが実現します。前者を奇置換、後者を偶置換といいます。

したがって、入れ換え回数を偶数にするか奇数にするかというところも乱数で決めないと、全部の順列に行き渡らないことになります。

No.4の方の質問ですが、(1,2,3)を2回入れ替える方法は9通りあります。9通りの中に(2,3,1) (3,1,2) (1,2,3) の3つの偶置換が3つずつ入っています。この場合はたまたま等確率ですが、(1,2,3,4)と要素を4つにすると入れ替えでは等確率にはなりません。

投稿日時 - 2005-02-27 12:59:08

お礼

奇置換、偶置換という言葉を初めて知りました。勉強になります。
いろいろ方法があるもんですね。一人で考えてると方法が偏ってしまって。
ありがとうございました。

投稿日時 - 2005-02-27 16:14:36

ANo.6

UKY

「ランダムに選んだ二つの数を入れ替える」を何度も繰り返す方法 (前の質問の 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 にはなりません。等確率ではない入れ替えを何度行っても、結果はやはり等確率にはならないのです。

投稿日時 - 2005-02-27 12:55:24

補足

お礼を下書きから写したときに余分なものが入ってしまいました。
> #6
なんかこれじゃ#6さんを呼び捨てにしてるみたいで。単なる間違いですので。

投稿日時 - 2005-02-27 16:07:38

お礼

#6
回答ありがとうございます。
> 値の入れ替えを何度繰り返せば ...
今回の件に限らず、「とりあえずできる」けど「本当にそれでいいのか」でよく悩みます。
こういうときに気軽に訊ける人がいればいいんですがね。

投稿日時 - 2005-02-27 16:06:40

ANo.5

重複しない乱数を発生させる方法としては、No.2の方の方法が一番オーソドックスです。
無駄な試行も無いですしロジックも比較的簡単です。
私もよく使っています。

前回の質問のNo.12の方の指摘は無視して結構です。
9通りのうち、自分自身を入れ替える3通りを除けばちゃんと6通りになりますし、
乱数としておかしくなる要素は全く有りません。
ただ、害は無いですが、自分自身を入れ替えるのは無駄ですね。

それと最後に余分な話ですが、重複の無い乱数と言うのは本当の乱数ではありません。
本当の乱数なら同じ数字が続く事もあるのです。
重複がないと言うことは単なる「シャッフル」ということで擬似乱数ですね。

投稿日時 - 2005-02-27 11:55:45

お礼

最後の「余分な話」ですが、余分ではなく、大変ためになります。
経験者の方の御意見はたいへん参考になります。
ありがとうございました。

投稿日時 - 2005-02-27 16:02:35

ANo.4

質問読みましたが、No.1およびNo.3に同意です。
元の質問のリンク先にある「9通り」「6通り」の意味がどうもよく分かりません。
あと「乱数」と「順番入れ替え」を整理して考える必要があると思います。
そもそも交換による「順番入れ替え」法は、トランプなどの「シャッフル」をプログラム上で実現させるためのアルゴリズムであって、乱数を発生させる方法ではないです。
「シャッフル」はカードを配り終えたときに、すべてのカードが均等に1回ずつ出現することが保証されなければなりませんが、「乱数」ではそのような保証はありません。というか、保証がある時点で「乱れた」数ではなくなってしまいます。

投稿日時 - 2005-02-27 11:30:29

お礼

回答ありがとうございます。
> あと「乱数」と「順番入れ替え」を整理して考える必要があると思います。
うーん、こういうところのあいまいさが間違いの原因なんでしょうね。

投稿日時 - 2005-02-27 15:58:22

ANo.3

私もNo.1(No.2)の方が書かれた方法がよいのでは、と考えています。というのも、これは例えば、0から99までの数字がそれぞれ書いてある100個のボールを、袋から「ランダム」に一つずつ(取ったボールは袋に戻さずに)100回取り出すことと同じ効果があると思えるからです。

ところで便乗質問なのですが、質問された方が以前投稿された回答(No.10)で、任意の2数を交換する手続きの回数が「十分大きい」場合、はじめの数字の並べ方の順番の影響が少なくなり、結果として得られる数列を「ランダム」といってもさしつかえなくなるのではないでしょうか? また、No.12の方が書かれている「9通り...6通り...」ということが、「ランダム」でない説明としてどのように関係しているのかわからないので、補足してくださる方がいれば幸いです。

いずれにしても、以下のNo.1の方が書かれた方法だと、手続きが(「十分に大きな回数」ではなく)100回で終わるので、やはりこの方法が効率的でよいかと私は思います。

投稿日時 - 2005-02-27 08:51:06

お礼

ありがとうございます。
OKWebを読んでると「こうすればできるよ」という回答はよく目に付くんですが、
あと一歩「どうしてこうするのか」が知りたいことがあるんですよね。

投稿日時 - 2005-02-27 15:55:00

ANo.2

前の私の回答は正確ではなさそうですので補足を。

0~Nの乱数を発生させてBが得られたら、A(B)の内容とA(N)の内容を交換します。
それからNを一つ減らす。
A(99)、A(98)、A(97)の順に発生した乱数を保存されるようになります。

投稿日時 - 2005-02-27 08:01:04

ANo.1

1.A(0)からA(99)までの配列を用意して、0から99までの値を入れておく。
2.0から99までの乱数を発生させる。
3.A(99)にその乱数を書き、その乱数の配列に99を書く。
4.0から98(ここがポイント)までの乱数を発生させる。
後は同じことを繰り返せばよいです。

最近のプログラマーは、このようなテクニックをあまり知らないようです。
言語の使い方ばかりは得意なようですが。

投稿日時 - 2005-02-27 07:31:20

お礼

なるほど。シンプルなことなんですね。ありがとうございました。

投稿日時 - 2005-02-27 15:51:45

あなたにオススメの質問