logo标签列表

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

c++algorithmrandomconstraintsunique
3
我有以下问题：
从0-N的范围内生成M个均匀随机整数，其中N>>M，并且没有一对整数的差小于K。目前我能想到的最好方法是维护一个排序列表，然后确定当前生成整数的下限，并测试它与下一个和上一个元素的关系，如果可以，则将元素插入其中。这是O(nlogn)的复杂度。
是否有更有效的算法？
问题示例：
在0到1亿之间生成1000个均匀随机整数，任意两个整数之间的差值不少于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

.

分布应该如何？可能的结果数是固定的。所有这些结果的概率应该相等吗？ - Vincent van der Weele
@Heuster：“分布应该如何处理？” 均匀分布。 - Soda Coader
1
我认为你的例子是无效的，因为1000 >> 1000不成立。 - Douglas Leeder
1
对一个包含数字在 0 和 N - (M - 1)*K + K 之间的数组进行 Fisher-Yates 洗牌，取结果数组的最后 K 个数字。这将给你一个大小为 K 的上述区间的均匀随机子集。你可以使用这个方法通过使用 K 子集作为 N - (M - 1)*K 的一元表示中的逗号来构建整数 N - (M - 1)*K 的 K + 1 组合（请参见此处以获得说明）。 - G. Bach
1
@G.Bach 可能会起作用，但边界条件可能会有问题。你能认真地写出来并将其发布为答案吗？（顺便说一句，生成随机子集的方法有更省空间的方式。） - David Eisenstat
显示剩余7条评论
3个回答
3

编辑: 我修改了文本，以满足创建具有相同概率的有序序列的要求。

创建不重复的随机数 a_i，其中 i=0..M-1。将它们排序。然后创建以下数字：

b_i=a_i + i*(K-1)

鉴于这个结构，那些数字 b_i 具有所需的间隔，因为 a_i 已经具有至少 1 的间隔。为了确保这些 b 值准确地覆盖所需的范围 [1..N]，您必须确保从范围 [1..N-(M-1)*(K-1)] 中选择 a_i。这样你就会得到真正独立的数字。尽管存在所需的间隔，但它们是尽可能独立的。由于排序，您再次获得 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
1
抱歉之前诋毁了这个答案。现在我仔细阅读后觉得它是正确的。 - David Eisenstat
2
思考一下，我不再确定这是否会产生均匀分布。该方法将每个排序序列(a_0,...,a_(M-1))映射到一个解集。为了获得解集(0,K,2K,...,(M-1)K)，您需要绘制序列(0,...,0)，其概率为(N-(M-1)*K)^(-M)。现在举个例子，取序列(1,1,2,3,...,M-1)的结果。与(0,...,0)相比，获得该序列的概率至少要大两倍，因为例如在排序之前你可以绘制(1,2,...,M-1,1)和(1,1,2,...,M-1)。这难道不应该给出更像正常分布的东西吗？ - G. Bach
1
对于你提供的算法，它需要在有效解集上产生均匀分布（这是我理解Soda Coader所寻找的），因此你必须均匀地绘制排序序列；否则，那些由具有更高概率的排序序列生成的解决方案就会存在偏差。你说你的算法可以产生均匀分布；但是在什么集合上呢？ - G. Bach
@G.Bach，它应该在组合上是均匀的。在发布的例子中，如果“次数”足够大，则分布应该导致所有组合具有相等（或接近相等）的被选择概率。 - Soda Coader
1
@G.Bach 不对。生日悖论是关于找到任何碰撞，而不是它们的频率。 只要占据的数字少于50％，碰撞的概率将保持在50％以下。 而这种情况适用于N>M*（K+1）。 - pentadecagon
显示剩余10条评论
2
首先：这将是一次尝试展示，在值为N - (M-1)*K的情况下，(M+1)个组成部分（稍作修改，允许有加数为0）与您问题的有效解之间存在双射。之后，我们只需要随机均匀地选择其中一个组成部分并应用双射即可。
双射：
设

M+1 - composition

然后，xi 构成左边值的一个 M+1 组合（可以有 0 个加数）（注意 xi 不必单调递增！）。
从这里我们得到了一个有效的解决方案。

solution set

通过设置如下的值mi:

construction composition to solution

我们看到mi和mi + 1之间的距离至少为K，而mM最多为N（与我们开始选择的组合进行比较）。这意味着每个满足上述条件的(M+1)组合都恰好定义了一个有效的解决方案。 （您会注意到，我们只使用xM来使总和正确，我们不使用它来构建mi。）
为了看到这给出了一个双射，我们需要看到构造可以被反转；为此，让

solution set

给定一个满足您条件的解决方案。要得到构建此解决方案所需的组合，请按以下方式定义xi：

construction solution to composition

首先，所有的 xi 至少为 0，所以这是正确的。要证明它们形成了上述给定值的有效组合（再次强调，每个 xi 都可以是 0），考虑以下内容：

enter image description here

第三个等式是由于我们有这个“卷积和”，它几乎消除了所有的mi。
因此，我们已经看到所描述的构造在描述的 N - (M-1)*K组合和您问题的有效解之间提供了一个双射。现在我们所要做的就是随机均匀地选择其中一个组合，并应用该构造来获得一个解决方案。
随机均匀选择一个组合。
每个描述的组合都可以通过以下方式唯一地识别（参见this以作说明）：为该值的一元表示保留N - (M-1)*K个空间，再为M个逗号保留M个空间。我们选择N - (M-1)*K + M个空间中的M个，在那里放置逗号，并用|填充其余部分，从而得到一个(M+1)-组合，其中x0是第一个逗号之前的|数，xM+1是最后一个逗号之后的|数，所有其他xi是逗号i和i+1之间的|数。因此，我们所要做的就是在整数区间[1; N - (M-1)*K + M]中均匀随机地选择一个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）。
2
抽取随机子集。我相信这个答案可以正确地抽取均匀样本。 - David Eisenstat
这是一种冗长但仍然非常有趣和全面的解释。谢谢你。 - Soda Coader
对于给定的N、M、K，考虑所有可行的组合，如果确定每个组合中相邻元素之间的(M-1)差异，那么连续差异的分布是否均匀？ - Soda Coader
@SodaCoader 我不确定我是否理解了这个问题。我们绘制的是由M个元素组成的解集，其中每个元素按排序顺序，其前驱和后继的距离至少为K。对于任何存在解集的(N,M,K)，可能的差分序列在有效解集中具有已知数量的出现次数，并且它们从delta序列到delta序列不同。例如，差分序列(K,K,...,K)在恰好N-(M-1)*K个有效解中出现，而差分序列(N-(M-1)*K,K,K,...,K)仅在一个有效解集中出现。 - G. Bach
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个随机数，均匀分布在N上，它们之间的差至少为K。时间复杂度为O(n)。额外的好处是已经排序了。:-)
编辑：
实际上，“选择一个随机数”的部分不应该在K和N/M之间，而应该在min(K，[K -（N/M * i-上一个值）])之间。这将确保差异仍然至少为K，并且不排除不应错过的值。
第二次编辑：
好吧，第一种情况不应该在K和N/M之间 - 应该在0和N/M之间。就像当您接近N/M * i边界时需要特殊处理一样，我们需要特殊的初始处理。
除此之外，在您的评论中提出的问题是公平表示，您是对的。按照我的伪代码呈现，它目前完全忽略了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。
  • 第1次迭代：在一个元素向量中随机选择一个元素，然后在该范围内随机选择一个元素。
    • 如果元素是，例如12345678，则我们移除[0...100Mill]并用[0...12344678]和[12346678...100Mill]替换它。
    • 如果元素是，例如500，则我们移除[0...100Mill]并将其替换为[1500...100Mill]，因为[0...500]不再是有效范围。唯一会替换成0范围的情况是，在极少数情况下您有一个仅包含一个数字的范围并且被选中。在那种情况下，您将连续拥有3个彼此相差K的数字。
    • 范围的权重是它们长度占总长度的比例，例如12344678/（12344678 +（100Mill - 12346678））和（100Mill - 12346678）/（12344678 +（100Mill - 12346678））
在接下来的迭代中，您需要做同样的事情：随机选择0到1之间的数字，并确定该尺度落入哪个范围内。然后在该范围内随机选择一个数字，并替换您的范围和尺度。
到完成时，我们不再是O(M)的操作，但我们仍然只依赖于M的时间而不是N。这实际上是均匀且公平的分布。
希望这些想法中的其中一个适合您！
@SodaCoader 我不能说它不会，但我认为你可以在 floor(N/M) 和 ceil(N/M) 之间变化足够多，以便你仍然可以相当公平地划分这些部分。但是，考虑到问题中的所有 ">>"，你是否有足够的样本来看出存在偏差？ - Scott Mermelstein
1
由于M = 3，我必须假设您指的是(1 5 9)和(1 5 10)。请注意，在这个例子中，我认为我们没有真正遵循“>>”（这很重要，因为分配问题甚至可以在大差异上平衡），但是您的示例确实提出了一些边界情况，我会在我的回答中解决。 - Scott Mermelstein
我不明白这个算法如何保证所有可能性的均匀分布。我认为它对低值有偏差。特别是，它如何生成“最高可能”的集合（n_(i+1) - n_i = K和n_M = N）？ - Vincent van der Weele
1
这些解决方案保证了分布的某种均匀性，而随机分布则没有；你会期望结果中有一些N/M倍数的间隙。在随机数的选择概率中通常希望均匀性，而不是它们的分布。 - Tony Delroy
2
这个解决方案无法为某些N、M、K的选择生成每个可能的解集。例如，取N=100，M=10000，K=10，则可能的解决方案是所有小于1000的10的倍数，但是这种方法永远无法生成它，因为它只在范围[1; 100]内生成一个数字。 - G. Bach
显示剩余4条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接