在一定范围内生成随机数，其中一定百分比为特定值。

Question

我需要创建大型随机图(请参阅下面的更多信息)，以比较Dijkstra、Bellman和Floyd的最短路径图遍历算法的性能。我将邻接存储在数组中。到目前为止，我在顶点之间生成了随机权值，并用0填充了主对角线。关于主对角线，我也有对称性(假设图是无向的，但不一定完全连通)。

随机值在0-24 ish范围内，使用rand() % 25生成.问题是，我希望图是稀疏的(即有较少的边)。有没有一种方法在一个范围内生成随机数，并且有大约1/3到1/2的生成数是一个特定值？注意，随机分布对我所做的事情并不重要.

另一个问题:我应该测试一个图形的大小来查看性能差异?10个顶点?100个?1000个? 10000000？

Answer 1

C++提供了discrete_distribution和uniform_int_distribution类，它们一起实现了您想要的结果。一个例子如下：

#include <random>
#include <iostream>

template<typename rgen>
int custom_random_int(rgen& mt) {
    // Returns 0 at a 1/3 chance, 1 at a 2/3 chance
    std::discrete_distribution<> d({1, 2});
    // Uniform distribution of integers in [0, 24]
    std::uniform_int_distribution<> ud(0, 24);
    if (d(mt) == 0) {
      // Return 0 at 1/3 chance
      return 0;
    } else {
      // Output a random number at 2/3 chance
      return ud(mt);
    }
}

int main() {
    // Fixed seed of 1 for demonstration purposes
    std::seed_seq ss{ 1 };
    std::mt19937 mt(ss);
    for(int i = 0; i < 100; i++) {
           std::cout << custom_random_int(mt) << std::endl;
    }
}