と金倶楽部

http://ap.atmarkit.co.jp/bbs/core/fjava/21486
http://d.hatena.ne.jp/issei_y/20100601/1275379705
http://chocobo.yasuda-u.ac.jp/~nisimura/mymove/index.cgi?no=1789

「ある会社から面接前にC#の宿題を出されました。一番効率良いのベストなコードを書いた方のみ面接するということでした。」...ということでその問題が以下の通りです...

「１から10,000の番号をランダムに生成するプログラムを作りなさい。プログラムを実行するごとに番号をランダムに生成すること。番号は重複使用しないこと。」

この問題は調べてみると意外と根が深いことが判明すますた...

最上リンクのページで様々な提案がでたのですが、中でも注目（？）を集めたのが以下のコードです。

　　　var random = new Random();
　　　source.OrderBy(_ => random.Next());

このコードの意図は「ソートを行うときに意図的に順序を決める部分（Ｃｏｍｐａｒａｔｏｒ）にデタラメな答えを出す（ランダム）様にする...よって、結果はランダムに成る」...なのですが、結論から言うと「これでは駄目」です。

http://www.robweir.com/blog/2010/02/microsoft-random-browser-ballot.html

上記の技法はマイクロソフトも”ランダム”な字列を作成するために用いたのですが結果としてはあまり”ランダム”に成らなかったのですね...

In this case Microsoft gave the following comparison function:

function RandomSort (a,b)
{
return (0.5 - Math.random());
}

Since Math.random() should return a random number chosen uniformly between 0 and 1, the RandomSort() function will return a random value between -0.5 and 0.5. If you know anything about sorting, you can see the problem here. Sorting requires a self-consistent definition of ordering. The following assertions must be true if sorting is to make any sense at all:

1. If a<b then b>a
2. If a>b then b<a
3. If a=b then b=a
4. if a<b and b<c then a<c
5. If a>b and b>c then a>c
6. If a=b and b=c then a=c

All of these statements are violated by the Microsoft comparison function. Since the comparison function returns random results, a sort routine that depends on any of these logical implications would receive inconsistent information regarding the progress of the sort. Given that, the fact that the results were non-random is hardly surprising. Depending on the exact search algorithm used, it may just do a few exchanges operations and then prematurely stop. Or, it could be worse. It could lead to an infinite loop.

ざ～っと訳すと、

マイクロソフトはソート用の比較に以下の関数を用いました。

function RandomSort (a,b)
{
return (0.5 - Math.random());
}

Math.random()　は０から１までの乱数を返すので　RandomSort()　はー0.5から＋0.5までの乱数を生成します。ソートについてそれなりに詳しい人ならば問題に気付くでしょう。ソートには以下の矛盾しない順番付けに関する公理を満たさなければなりません。

1. If a<b then b>a
2. If a>b then b<a
3. If a=b then b=a
4. if a<b and b<c then a<c
5. If a>b and b>c then a>c
6. If a=b and b=c then a=c

マイクロソフト作成の関数（RandomSort()）はこの点において全てに違反しています。よってこの関数は（同じパラメターで関数を呼び出しても）矛盾した情報を返すことができるためソートがどの程度進んでいるかを計ることができません。従ってソートに使われたアルゴリズム次第では数回数字を交換して終わる...なんてこともありえますし、最悪の場合には無限ループに陥ります。

...と言う訳で「これでは駄目」です。詳細はリンクから読むべし。

では模範回答（？）はどうあるべきか？？？

まず問題を振り返りましょう。

「１から10,000の番号をランダムに生成するプログラムを作りなさい。プログラムを実行するごとに番号をランダムに生成すること。番号は重複使用しないこと。」

...色々書いてありますが、この問題の意図は「番号をランダムに生成する」のではなく、「１から10,000の番号をランダムにシャッフルせよ」...ということに成ります。トランプをシャッフルして一枚一枚捲っていくのと同じですね。

（（初級））

１．１から10,000の番号を行列に書き込む
２．ランダムに二つ選んで交換する。
３．（２）を適当な回数繰り返す

...お手軽に実装できますが、「ランダム度」は交換の回数によります。一応問題の条件を満たしますが、試験官はそれほど関心しないでしょう。

（（中級））

１．１から10,000の番号を行列に書き込む
２．ランダムに一つ選ぶ...そしてその数字を記録する。
３．（２）で選んだ数字を行列から消す...つまり、行列の「間」を詰める
４．数字が無くなるまで（２）　と（３）を繰り返す

...一応問題の条件を満たしますし、「ランダム度」も高くなります。ですが『行列の「間」を詰める』のは意外と時間の浪費になります。

（（上級））　（だと思う）

１．１から10,000の番号を行列に書き込む
２．ランダムに一つ選ぶ...そしてその数字を記録する。
３．（２）で選んだ数字を行列から消す...　行列の最後の数字で上書きします。そして行列のサイズを一つ縮める。（正確には行列の最後の位置を覚えておく...ですね。）
４．数字が無くなるまで（２）　と（３）を繰り返す

...一応問題の条件を満たしますし、「ランダム度」も高くなります。　上記に上げた欠点も直しています。　Ｏ（ｎ）　です。