重複しない乱数の生成

Question

他の質問での回答に対してもう少し具体的に知りたいと思って投稿しました。

自分はいわゆる日曜プログラマです。
勉強のつもりで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]まで入れて終了。

過去の質問を覗いてみましたが、いろいろな方法があってどれがいいのか迷ってきま
した。どちらかというと具体的なソースではなく考え方を教えてください。

よろしくお願いします。

BLUEPIXY · Accepted Answer

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

bender · Answer

#3　です。
質問文を読み返すと、質問された方が書かれているアイディアは、#1の方と、考え方としては同じであることに気づき、私の説明は蛇足であったと思いました。問題文を注意深く読まず失礼しました。

#7　の方が計算されているのですが、「入れ替え法」は、Ｎ個の要素があるとき、Ｎ！の状態（並び方）を遷移する　Markov Chain　という確率過程ではないでしょうか（参考ＵＲＬ）。各状態からの遷移確率が「同じように」なっているので、収束する際には、ある状態（並び方）にある確率が同じになるはずでは、と考えました。

既出ですが、「入れ替え法」では最低Ｎ－１回の入れ替えをしないことにはたどり着けない並び方があるように思います（要素が一個づつずれたような並び方）。

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

shkwta · Answer

#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倍になります。

どうやら、確率の不均等は指数関数的に減少するようですが、証明があるかどうかはわかりません。

UKY · Answer

誤解があるといけないので、補足。

shkwta さんのおっしゃる偶置換・奇置換の話は、私や BLUEPIXY さんが考えている入れ替えとは前提条件が違います。
私や BLUEPIXY の話に出てくる入れ替えには「同じ数同士を入れ替える」つまり「実質的には入れ替えないのと同じ」パターンが含まれているのに対し、shkwta さんの話ではこのパターンを含みません。

例えば、同じ数同士を入れ替えるパターンを含む入れ替えを考える場合に、偶置換・奇置換の違いを考えるのは意味がないということです。(前提条件がごっちゃになっている)

以上、文面から誤解する人がいるかもしれないと思ったのでちょっと補足しました。

shkwta · Answer

入れ替え法について補足します。

有限回の入れ替えでは、すべての順列が厳密には等確率にはなりませんが、回数を多くすると限りなく等確率に近づきます。しかし、各入れ替えごとに、順列のうち半分しか実現しないことに注意が必要です。

たとえば、(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 · Answer

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

ymmasayan · Answer

重複しない乱数を発生させる方法としては、No.2の方の方法が一番オーソドックスです。
無駄な試行も無いですしロジックも比較的簡単です。
私もよく使っています。

前回の質問のNo.12の方の指摘は無視して結構です。
９通りのうち、自分自身を入れ替える３通りを除けばちゃんと６通りになりますし、
乱数としておかしくなる要素は全く有りません。
ただ、害は無いですが、自分自身を入れ替えるのは無駄ですね。

それと最後に余分な話ですが、重複の無い乱数と言うのは本当の乱数ではありません。
本当の乱数なら同じ数字が続く事もあるのです。
重複がないと言うことは単なる「シャッフル」ということで擬似乱数ですね。

hide9048 · Answer

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

bender · Answer

私もＮｏ．１（Ｎｏ．２）の方が書かれた方法がよいのでは、と考えています。というのも、これは例えば、０から９９までの数字がそれぞれ書いてある１００個のボールを、袋から「ランダム」に一つずつ（取ったボールは袋に戻さずに）１００回取り出すことと同じ効果があると思えるからです。

ところで便乗質問なのですが、質問された方が以前投稿された回答（Ｎｏ．１０）で、任意の２数を交換する手続きの回数が「十分大きい」場合、はじめの数字の並べ方の順番の影響が少なくなり、結果として得られる数列を「ランダム」といってもさしつかえなくなるのではないでしょうか？　また、Ｎｏ．１２の方が書かれている「９通り...６通り...」ということが、「ランダム」でない説明としてどのように関係しているのかわからないので、補足してくださる方がいれば幸いです。

いずれにしても、以下のＮｏ．１の方が書かれた方法だと、手続きが（「十分に大きな回数」ではなく）１００回で終わるので、やはりこの方法が効率的でよいかと私は思います。

cyoki_par · Answer

前の私の回答は正確ではなさそうですので補足を。

０～Ｎの乱数を発生させてＢが得られたら、Ａ（Ｂ）の内容とＡ（Ｎ）の内容を交換します。
それからＮを一つ減らす。
Ａ（９９）、Ａ（９８）、Ａ（９７）の順に発生した乱数を保存されるようになります。

重複しない乱数の生成

>元の質問のリンク先にある「9通り」「6通り」の意味がどうもよく分かりません。

この回答への補足

#3 です。

#7です。

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

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

「ランダムに選んだ二つの数を入れ替える」を何度も繰り返す方法 (前の質問の masa_pee さんの方法) がいけないのは、100% ランダムなシャッフルができない、という点です。

この回答への補足

重複しない乱数を発生させる方法としては、No.2の方の方法が一番オーソドックスです。

質問読みましたが、No.1およびNo.3に同意です。

私もＮｏ．１（Ｎｏ．２）の方が書かれた方法がよいのでは、と考えています。

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

似たような質問が見つかりました

このQ&Aを見た人はこんなQ&Aも見ています

関連するカテゴリからQ&Aを探す

このQ&Aを見た人がよく見るQ&A

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

#3　です。