効率的に：固定された範囲の乱数は繰り返しなし

Question

乱数には100万の質問がありますが、私はたくさんの検索をしましたが、私のようなものは見つけられませんでした。いない。いずれにしても、私が質問を繰り返す場合は私を許してください。そうであれば私にそれを指摘してください。

私は最も効率的な方法で簡単なことをしたいと思います。

[0, N]の範囲の整数をすべてランダムに生成したいので、繰り返しはありません。

私はlistにすべてを挿入し、シャッフルして頭を取り出し、リストから頭を取り除くことでこれを行うことができます。しかし、私は長さN、N-1回の私のリストをシャッフルします。

もっと速く/速いアイデアはありますか？

Answer 1

シャッフルを1回だけ実行してから、リストをステップ実行することができます。

Fisher-Yates shuffleをお勧めします。

Answer 2

この質問は何度か尋ねられていますが、正しい答えは配列（元の配列またはインデックスの配列）をシャッフルすることですが、これは満足できる答えです。可能なインデックスの数が非常に多い（巨大である、またはメモリが逼迫している、または何らかの理由で最大効率を渇望している）。

このように私は完全性のために代替案を追加したいと思います。さて、これは本当にランダムではないので、もしそれがあなたが必要とするものなら、はこのを使わないでください。しかし、あなたの目標が最小限のメモリ要件で "十分"であれば、次の擬似コードが重要です。

function init: 
    start = random [0, length)  // Pick a fully random starting index 
    stride = random [1, length - 1) // Pick a random step size 
    next_index = start 

function advance_next_index: 
    next_index = (next_index + stride) % length 
    if next_index is equal to start then 
     start = (start + 1) % length 
     next_index = start 

ここで擬似ランダムな値をつかむために再利用可能な機能を実装する方法の例です：

counter = length 
function pseudo_random: 
    counter = counter + 1 
    if counter is equal to length then 
     init() 
     counter = 0 
    advance_next_index() 
    return next_index 

かなり単にpseudo_randomは、このように「ランダム再シャッフル、init回length反復を呼び出します。 "によって生成された結果のパターンを入力し、lengthの値ごとに1つの複製がないことを確認してください。

繰り返します。これは特にランダムなアルゴリズムではないので、真のランダム性が必要な状況でを使用してはならない。しかし、結果はいくつかの基本的で非クリティカルなタスクでは十分にランダムであり、小さなメモリフットプリントしか持たない。たとえば、何かが繰り返されるのを避けるためにゲーム内でいくつかの動作をランダム化したい場合や、データセットが大きく、決してユーザーに公開されないような場合（その場合、効果的にランダムになります）注文をまとめて何とかそれを悪用する。

誰もが同様のプロパティを持つより良いアルゴリズムを知っている場合は、共有してください！