直列化可能なソート済み整数を出力する

Question

ランダムに選択された正の整数のリストをソート順で生成したいと思っていますが、必要な整数の数と指定されたユースケースから選択できる数値の範囲は、何百万もの（場合によっては、64ビット整数が使用されている場合は、数十億の範囲内でさえも）、その数値を配列に格納してソフトウェアでランダムにアクセスすることは実際には実行可能ではありません。

したがって、私はこのような何かに見えた単純なループを経由して数値を生成したい：

unsigned current = 0; 
while(remaining>0) { 
    if (find_next_to_output(current,max,remaining)) { 
     // do stuff having output a value   
    } 
} 

remainingは私が出力するつもりしかし、多くの乱数に初期化され、そしてmaxは（上限ありプラス1）を生成することができます。 remainingは常にmax以下の数値に初期化されると想定できます。

find_next_to_output関数は次のようになります

/** 
* advance through the range of accepted values until all values have been output 
* @param current [in/out] integer to examine. Advances to the next integer 
* to consider for output 
* @param max one more than the largest integer to ever output 
* @param remaining [in/out] number of integers left to output. 
* @return true if the function ouputted an integer, false otherwise 
*/ 
bool find_next_to_output(unsigned &current, unsigned max, unsigned &remaining) 
{ 
    bool result = false; 
    if (remaining == 0) { 
     return false; 
    } if (rnd() * (max - current) < remaining) { 
     // code to output 'current' goes here. 
     remaining--; 
     result = true; 
    } 
    int x = ?; // WHAT GOES HERE? 
    current += x; 
    return result; 
} 

注、上記使用関数rnd()がランダム範囲[0..1）上の浮動小数点数を生成し均一に返します。コメントのハイライトとして

、私は関数で飛ばしますcurrentの値の数がスキップされた値の確率はどれを反映しているように、xのための合理的な値を計算する方法がわかりませんよ（残っている残りの数字を残して残りの数字を残しておくことができます）。私はそれが乱数である必要があることを知っています（おそらく一様分布からではないかもしれませんが）、私はそれに対して良い値を計算する方法を知らないのです。最悪の場合、毎回currentを1つずつインクリメントするだけですが、残っている整数の数とその範囲に残っている整数の数に十分な差がある場合、統計的にはそうはならないはずです。

C++ 11用の標準ライブラリにパックされている乱数ジェネレータを使用しても問題ありませんが、私はboostなどのサードパーティライブラリを使用したくありません。

私の質問の一部が不明な場合は、以下にコメントしてください。私は明確にするよう努力します。

Answer 1

私が正しく理解している場合は、ランダムな昇順の数字を生成したいと考えています。前の番号に追加するランダムなサイズのステップを作成して、これを実行しようとしています。

あなたの心配は、ステップが大きすぎる場合はオーバーフローして折り返して、上昇する要件を破ることです。

xは、オーバーフローを防ぎ、ランダム要求を満たしている必要があります。

modulo演算子（係数）が必要です。 %

const unsigned step = (max - current)/remaining; 

x = unsigned(rnd() * max) % step; // will never be larger than step