c++ - 生成具有差异约束的随机整数

Question

我有以下问题:

从 0-N 范围内生成 M 个均匀随机整数，其中 N >> M，并且没有对的差值小于 K。其中 M >> K。

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

会不会有更高效的算法？

问题示例:

生成1000个0到1亿之间的均匀随机整数，其中任意两个整数之差不小于1000

解决此问题的综合方法是:

1. 确定满足约束条件的n-choose-m的所有组合，称其为集合X
2. 选择[0,|X|]范围内的均匀随机整数i。
3. 从 X 中选择第 i 个组合作为结果。

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

注意:下面是pentadecagon提供的方案的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

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

为 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