输出可序列化的排序整数

Question

我想按排序顺序生成随机选择的正整数的序列化列表，但是在给定用例中所需的整数数和可能从中选择的数字范围很容易达到数百万(如果使用 64 位整数，有时甚至每个都在数十亿范围内)， 因此，将数字存储到一个数组中然后可以通过软件随机访问实际上是不可行的。

因此，我想通过一个简单的循环生成数字，看起来像这样：

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

其中remaining初始化为我打算输出的随机数，max是可能生成的数字的上限(加一)。 可以假设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) 上返回一个统一的随机生成的浮点数。

正如评论所强调的那样，我不确定如何计算x的合理值，以便函数跳过的current值的数量反映了没有跳过的值被选择的概率(同时仍然留下足够的数字，仍然可以选择所有剩余的数字)。我知道它需要是一个随机数(可能不是来自均匀分布)，但我不知道如何为它计算一个好的值。 在最坏的情况下，它只是每次将current递增 1，但当要输出的剩余整数数与范围内剩余的整数数之间存在足够的差异时，这在统计上应该不太可能。

我不想使用任何第三方库，例如 boost，尽管我可以使用任何可能打包在 C++11 标准库中的随机数生成器。

如果我的问题有任何部分不清楚，请在下面发表评论，我将努力澄清。

Answer 1

如果我理解正确，您希望生成随机的升序数字。 您正在尝试通过创建一个随机大小的步长来添加到前一个数字中来执行此操作。

你担心的是，如果步长太大，那么你就会溢出并绕回去，打破升序要求。

x需要以防止溢出的方式进行约束，同时仍满足随机要求。

您需要modulo运算符(模数)。%

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