[解決済み] 一意な（繰り返しのない）乱数をO(1)で？

質問

0から1000の間で、決して繰り返さない（つまり6が2回現れない）ユニークな乱数を生成したいのですが、そのために以前の値のO（N）検索のようなものに頼らないで済みます。これは可能でしょうか？

解決方法は？

1001個の整数からなる配列を0〜1000の値で初期化し、変数maxに配列の現在の最大インデックス（1000で始まる）を設定する。 0からmaxの間で乱数rを選び、rの位置の数値とmaxの位置の数値を入れ替え、現在のmaxの位置の数値を返す。 maxを1つ減らし、処理を継続する。 maxが0になったら、maxを配列のサイズ-1に戻し、配列を再初期化する必要なく、再び開始します。

更新します。 この方法は、質問に答えるときに勝手に思いついたのですが、いろいろと調べてみると、これは フィッシャー・イェーツ Durstenfeld-Fisher-Yates、Knuth-Fisher-Yatesと呼ばれるものです。 少し説明がわかりにくいかもしれませんので、以下に例を示します（1001の代わりに11の要素を使っています）。

配列は array[n] = n で初期化された11個の要素で始まり、最大値は10で始まります。

+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|
+--+--+--+--+--+--+--+--+--+--+--+
                                ^
                               max    

反復毎に，0 から max までの乱数 r が選択され， array[r] と array[max] が入れ替わり，新しい array[max] が返され，max がデクリメントされます．

max = 10, r = 3
           +--------------------+
           v                    v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2|10| 4| 5| 6| 7| 8| 9| 3|
+--+--+--+--+--+--+--+--+--+--+--+

max = 9, r = 7
                       +-----+
                       v     v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2|10| 4| 5| 6| 9| 8| 7: 3|
+--+--+--+--+--+--+--+--+--+--+--+

max = 8, r = 1
     +--------------------+
     v                    v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 8| 2|10| 4| 5| 6| 9| 1: 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+

max = 7, r = 5
                 +-----+
                 v     v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 8| 2|10| 4| 9| 6| 5: 1| 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+

...

11回繰り返した後、配列のすべての数字が選択され、max == 0となり、配列の要素がシャッフルされます。

+--+--+--+--+--+--+--+--+--+--+--+
| 4|10| 8| 6| 2| 0| 9| 5| 1| 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+

この時点で、maxを10にリセットし、処理を継続することができます。