これは、就職の面接での質問に触発されました。N個の一意の乱数を効率的に生成するにはどうすればよいですか。それらのセキュリティと配布/バイアスは重要ではありません。
rand（）をN回呼び出し、試行錯誤によって重複を排除するという単純な方法を提案しました。これにより、非効率で欠陥のあるソリューションが得られます。次に、このSOの質問を読みました。これらのアルゴリズムは、高品質の一意の数値を取得するのに最適であり、O（N）です。
しかし、O（N）時間計算量未満で、ダミータスクの低品質の一意の乱数を取得する方法があると思います。私はいくつかの可能なアイデアを得ました：
- それぞれがN個の数値を含む多くの事前計算されたリストを保存し、1つのリストをランダムに取得します。複雑さは、固定Nの場合はO（1）です。使用されるストレージスペースはO（NR）です。ここで、Rはリストの数です。
- N / 2個の一意の乱数を生成し、それらを2つの等しくない部分で除算します（奇数の場合は床/天井、偶数の場合はn + 1 / n-1）。これには欠陥があり（重複がポップアップする可能性があります）、O（N / 2）はまだO（N）です。これは思考の糧です。
- 1つの大きな乱数を生成し、ビット単位の演算、因数分解、再帰、MapReduceなどの固定操作によって、そこからさらに多くのバリアントを絞り出します。
- どういうわけか準ランダムシーケンスを使用します（数学者ではなく、この用語をグーグルで検索しただけです）。
あなたのアイデアは？