algorithm - 最初の n 個の自然数のランダム順列を生成する最も効率的な方法は何ですか?

Question

今まで、遭遇したすべての一意の番号を追跡するリストを使用してきました。乱数ジェネレーターを使用して、1 から n の間の乱数を取得しています。その番号が既にリストにある場合は、リストにない番号に遭遇するまで乱数を生成し続けます。リストにない新しい番号を取得したら、それをリストに追加し、「n」個の番号がすべてリストに含まれるまでこのプロセスを繰り返します。

明らかに、この方法は非常に非効率的です。誰かがこれに対する効率的な解決策を提案できますか??

Answer 1

他のアルゴリズムも利用できますが、Knuthがこれに対応します。

Answer 2

• 1 から N までの番号で番号付きリストを作成します。
• それをシャッフルします (つまり、順列を作成します)。これは線形時間で実行できます (このアルゴリズムを参照してください)。