C ++如何生成10,000个UNIQUE随机整数来存储在BST中？

Question

我试图在1到20,000的范围内生成10,000个唯一的随机整数来存储在BST中，但不确定最佳方法。

我看到了一些关于如何使用数组或向量进行此类操作的好建议，但对于BST则没有。我有一个contains方法，但我不相信它会在这种情况下工作，因为它用于搜索并返回找到所需数字所需的尝试次数的结果。下面是我最接近但它不喜欢我的==操作员。使用数组并将数组存储在BST中会更好吗？或者是否有更好的方法来使用下面的代码，以便在生成数字时，它只是将它们存储在树中？

for (int i = 0; i < 10000; i++) 
{
    int random = rand() % 20000;
    tree1Ptr->add(random);
    for (int j = 0; j < i; j++) {
        if (tree1Ptr[j]==random) i--;
        }
    }

Answer 1

您的代码中存在一些问题。但是，让我们直截了当地说明这一点。

主要问题是什么？

从您的代码中可以看出，tree1Ptr是一个指针。原则上，它应该指向树的一个节点，它有两个指针，一个指向左节点，一个指向右节点。

所以你的代码中应该有：

tree1Ptr = new Node;   // or whatever the type of your node is called

但是，在你的内部循环中，你只是使用它就好像它是一个数组：

for (int i = 0; i < 10000; i++) 
{
    int random = rand() % 20000;
    tree1Ptr->add(random);
    for (int j = 0; j < i; j++) {
        if (tree1Ptr[j]==random)  //<============ OUCH !!
            i--;
    }
}

编译器不会抱怨，因为它是有效的语法：您可以在指针上使用数组索引。但是你要确保你不要超出界限（所以在这里，j仍然<1）。

其他言论

顺便说一下，在内循环中，你只想说如果找到了数字就必须重试。如果已找到数字，你可以break内循环，以便不继续。

您还应该为随机数生成器播种，以避免始终以相同的顺序运行程序。

怎么解决？

你真的需要加深对BST的理解。浏览节点需要与当前节点中的值进行比较，并根据结果迭代继续使用左指针或右指针，而不是使用索引。但这里要解释太久了。所以你应该寻找一个教程，比如this one

Answer 2

对于许多独特的“随机”数字，我通常使用Format Preserving Encryption。由于加密是一对一的，只要输入是唯一的，就可以保证唯一的输出。不同的加密密钥将生成不同的输出集，即输入的不同排列。只需加密0,1,2,3,4 ......，输出就可以保证唯一。

您想要的数字在[1 .. 20,000]范围内。不幸的是，20,000需要21位，大多数加密方案都有偶数位：在你的情况下是22位。这意味着你需要骑自行车;如果数字太大，则重新加密输出，直到获得所需范围内的数字。由于您的输入仅达到10,000并且您将循环行走超过20,000，您仍将避免重复。

我知道唯一允许22位块大小的标准密码是Hasty Pudding密码。或者，很容易编写自己的简单Feistel cipher。如果您不想要加密安全性，那么四轮就足够了。对于加密级安全性，您需要使用经过NIST批准的AES / FFX。

Answer 3

有两种方法可以从序列中挑选随机唯一数字，而无需检查先前选取的数字（即已经在您的BST中）。

Use random_shuffle

一种简单的方法是将1到20,000的排序数组洗牌，然后简单地选择前10,000个项目：

#include <algorithm>
#include <vector>

std::vector<int> values(20000);
for (int i = 0; i < 20000; ++i) {
  values[i] = i+1;
}
std::random_shuffle(values.begin(), values.end());

for (int i = 0; i < 10000; ++i) {
  // Insert values[i] into your BST
}

如果要挑选的随机数（10,000）的大小与总数（20,000）的大小相当，则此方法很有效，因为随机混洗的复杂性在较大的结果集上摊销。

Use uniform_int_distribution

如果要选择的随机数的大小远小于总数的大小，则可以使用另一种方法：

#include <chrono>
#include <random>
#include <vector>

// Use timed seed so every run produces different random picks.
std::default_random_engine reng(
    std::chrono::steady_clock::now().time_since_epoch().count());

int num_pick  = 1000;   // # of random numbers remained to pick
int num_total = 20000;  // Total # of numbers to pick from

int cur_value = 1;  // Current prospective number to be picked
while (num_pick > 0) {
  // Probability to pick `cur_value` is num_pick / (num_total-cur_value+1)
  std::uniform_int_distribution<int> distrib(0, num_total-cur_value);

  if (distrib(reng) < num_pick) {
    bst.insert(cur_value);  // insert `cur_value` to your BST
    --num_pick;
  }
  ++cur_value;
}