生成随机整数与差约束

Question

我有以下问题：

产生m个由范围为0-N，其中N >> M，且其中没有对具有差小于K. 均匀随机整数其中M >> K 。

目前我能想到的最好的方法是维护一个排序列表，然后确定当前生成的整数的下界，并用下方和上方元素进行测试，如果可以插入元素之间。这是复杂的O（nlogn）。

会碰巧有更高效的算法吗？

的问题的一个例子：

生成零和1亿，其中任何两个整数之间的差不小于1000

全面的方式来解决，这将是到1000个之间的均匀随机整数：

1. 确定的正选择-M满足约束的所有组合，让称为它设置X
2. 在范围[0，选择均匀随机整数i，| X |）。
3. 从X中选择第i个组合作为结果。

当n选择m很大时，此解决方案有问题，因为枚举和存储所有可能的组合将会非常昂贵。因此寻求高效的在线生成解决方案。

注：下面是一个C++实现由提供的解决方案的十五边形

std::vector<int> generate_random(const int n, const int m, const int k) 
{ 
    if ((n < m) || (m < k)) 
     return std::vector<int>(); 

    std::random_device source; 
    std::mt19937 generator(source()); 
    std::uniform_int_distribution<> distribution(0, n - (m - 1) * k); 

    std::vector<int> result_list; 
    result_list.reserve(m); 

    for (int i = 0; i < m; ++i) 
    { 
     result_list.push_back(distribution(generator)); 
    } 

    std::sort(std::begin(result_list),std::end(result_list)); 

    for (int i = 0; i < m; ++i) 
    { 
     result_list[i] += (i * k); 
    } 

    return result_list; 
} 

http://ideone.com/KOeR4R

。

Answer 1

为什么不能做到这一点：

for (int i = 0; i < M; ++i) { 
    pick a random number between K and N/M 
    add this number to (N/M)* i; 

现在你有m个随机数字，沿ñ均匀分布，所有这些都至少K.这是一个在O（n）的时间差。作为额外的奖励，它已经排序。 :-)

编辑：

实际上， “选择一个随机数” 部分不应该K和N/M之间，但min(K, [K - (N/M * i - previous value)])之间。这将确保差异至少为K，并且不排除不应忽略的值。

第二编辑：

好，第一种情况下不应该是K和N/M之间 - 它应该是0和N/M之间。就像您在接近N/M *边界时需要特殊外壳一样，我们需要特殊的初始套管。

除此之外，你在评论中提出的问题是公平的代表性，你是对的。当我的伪代码被提交时，它现在完全忽略了N/M * M和N之间的过量。这是另一个边缘案例;只需更改最后一个范围的随机值。

现在，在这种情况下，您的分配将在最后一个范围内有所不同。由于你有更多的号码，每个号码的机会比所有其他范围的机会略少。我的理解是，因为你使用“>>”，这不应该真正影响分布，即样本集中的大小差异应该是标称的。但是如果你想让它更公平，你可以在每个范围内平均分配多余的钱。这使得你的初始范围计算更复杂 - 你必须根据M除以多少余数来增加每个范围。

有很多特殊情况需要注意，但它们都能够被处理。我保持这个伪代码非常基本，以确保总体概念清晰。如果没有别的，它应该是一个很好的起点。

第三个也是最后编辑：

对于那些担心分布具有强制均匀性，我仍然声称没有什么说，它不能。选择均匀分布在每个分段中。有一个线性的方法来保持它的不平衡，但也有一个折衷：如果选择一个非常高的值（对于非常大的N应该不太可能），那么所有其他值都受到限制：

int prevValue = 0; 
int maxRange; 
for (int i = 0; i < M; ++i) { 
    maxRange = N - (((M - 1) - i) * K) - prevValue; 
    int nextValue = random(0, maxRange); 
    prevValue += nextValue; 
    store previous value; 
    prevValue += K; 
} 

这仍然是线性和随机的，并允许不均匀性，但更大的prevValue得到，其他数字变得越受约束。就个人而言，我更喜欢我的第二个编辑答案，但这是一个可用的选项，如果足够大，N很可能会满足所有发布的要求。

想想吧，这里有一个其他的想法。它需要更多的数据维护，但仍然是O（M），并且可能是最公平的分布：

您需要做的是维护有效数据范围的向量和概率尺度的向量。有效的数据范围只是K仍然有效的高低值列表。这个想法是你首先使用缩放的概率来选择一个随机的数据范围，然后你随机选择一个范围内的值。您可以删除旧的有效数据范围，并将其替换为0,1或2个新的数据范围，具体取决于有多少个仍然有效。除了处理加权概率O（M），在循环中执行M次，所有这些操作都是恒定时间，因此总数应该是O（M^2），这应该比O（NlogN）好得多，因为N >> M.

而不是伪代码，让我用OP原来的工作，例如一个例子：

• 0次迭代：有效的数据范围为[0 ... 100Mill]，重量为这个范围是1.0。
• 第一次迭代：随机选取一个元素向量中的一个元素，然后随机选取该范围中的一个元素。
  • 如果元素是，例如， 12345678，然后我们删除[0 ... 100Mill]并用[0 ... 12344678]和[12346678 ... 100Mill]
  • 替换它。 500，然后我们删除[0 ... 100Mill]并用[1500 ... 100Mill]替换它，因为[0 ... 500]不再是有效范围。我们唯一一次将其替换为0的范围是不太可能的，因为您只有一个范围，并且它被选中。 （在这种情况下，连续3个数字彼此完全相距K）。
  • 范围的权重是它们在总长度上的长度e。G。 12344678 /（12344678 +（100Mill - 12346678））和（100Mill - 12346678）/（12344678 +（100Mill - 12346678））

在接下来的迭代中，你做同样的事情：随机挑选一个数字在0和1之间，并确定哪些范围落入。然后在该范围内随机选取一个数字，并替换您的范围和比例。当它完成时，我们不再在O（M）中动作，但是我们仍然只依赖于M的时间而不是N.这实际上是均匀和公平的分布。

希望这些想法之一适合你！

Answer 2

编辑：我调整了要求创建有序序列的文本，每个都有相同的概率。

为i=0..M-1创建随机数a_i而不重复。对它们排序。然后创建一个数字

b_i=a_i + i*(K-1) 

鉴于建设，这些b_i具有所需缺口数字，因为a_i已经有至少1差距。为确保这些b值完全覆盖了要求的范围[1..N]，您必须确保a_i从[1..N-(M-1)*(K-1)]范围内挑选。这样你就可以得到真正独立的数字。那么，考虑到所需的差距，尽可能独立。由于排序，您可以再次获得O（M log M）性能，但这应该不会太差。排序通常非常快。在Python它看起来像这样：

import random 
def random_list(N, M, K): 
    s = set() 
    while len(s) < M: 
     s.add(random.randint(1, N-(M-1)*(K-1))) 

    res = sorted(s) 

    for i in range(M): 
     res[i] += i * (K-1) 

    return res 

Answer 3

第一关：这将是表明还有的(M+1)之间的一一对应的尝试 - compositions（有轻微修改，我们将允许加数是0）的价值N - (M-1)*K和您的问题的有效解决方案。之后，我们只需要随机选择一种组合物并应用双射。

---

双向注入：

让

那么X _我形成M+1组成 - ·（具有允许0加数）的值的左侧（通知那个x _i不一定是单调的压痕！）。

由此我们得到一个有效的解决方案

通过设置值M _我如下：

我们看到是m _我之间的距离和m _{i + 1}至少为K和m _M最多为N（比较我们开始使用的组合物的选择）。这意味着每个满足上述条件的组合都会为您的问题定义一个有效的解决方案。 （你会发现，我们只使用x _中号作为一种方法，使之变成正确的，我们不使用它的m个_我建设。）

一看就知道给出一个双射，我们需要看到这个构造可以颠倒过来;为了这个目的，让

是一个给定的解决方案满足您的条件。为了得到这个从构建组成，如下定义X _我：

现在首先，所有的X _我至少0，所以这是正常的。看到他们形成有效成分（再次，每x _我允许为0）上面给出的值，可以考虑：

第三平等如下，因为我们有这样的伸缩总和是几乎消除了所有的m _i。

所以我们已经看到，描述的结构给出了所描述的N - (M-1)*K的组合与您的问题的有效解决方案之间的双射。我们现在要做的就是随机挑选其中一种组合物，然后使用这种结构来获得解决方案。

---

采摘的组合物均匀地随机

每一个都可以以下面的方式被唯一标识，所述的组合物的（比较this用于说明）：储备N - (M-1)*K空间用于该值的一元表示法，和另一个M空格用于M逗号。我们得到一个(M+1) - 组成N - (M-1)*K通过选择N - (M-1)*K + M空间的M，把逗号放在那里，并填写其余的|。然后让X 是第一个逗号之前的|数，X _{M + 1}的|最后一个逗号之后的数量，并且所有其它的X _我的|逗号i和i+1之间的数量。因此，我们所要做的就是随机选择一个整数区间[1; N - (M-1)*K + M]的元素子集，我们可以使用例如Fisher-Yates shuffle在O(N + M log M)（我们需要对M分隔符进行排序以构建组合） M*K需要在O(N)存在任何解决方案。因此，如果N至少以对数因子大于M，那么这在N中是线性的。

---

注：@DavidEisenstat建议，有更多的空间采摘间隔M - 元素的子集的有效途径;我不知道有任何恐惧。

---

你可以做简单的输入验证我们从N ≥ (M-1) * K以上建设得到得到一个错误验证算法出这一点，所有这三个值至少1（或0，如果定义空作为该案件的有效解决方案）。