C++ 非重复随机数发生器

Non-repeating random number generator

提问by Jpeh Noynay

I'd like to make a number generator that does not repeat the number it has given out already (C++).

我想制作一个数字生成器，它不会重复它已经给出的数字（C++）。

All I know is:

我所知道的是：

int randomgenerator(){
  int random;
  srand(time(0));
  random = rand()%11;
  return(random);
} // Added this on edition

That function gives me redundant numbers.

该函数给了我多余的数字。

I'm trying to create a questionnaire program that gives out 10 questions in a random order and I don't want any of the questions to reappear.

我正在尝试创建一个问卷程序，以随机顺序给出 10 个问题，我不希望任何问题再次出现。

Does anyone know the syntax?

有人知道语法吗？

回答by The Communist Duck

What I would do:

我会怎么做：

• Generate a vector of length N and fill it with values 1,2,...N.
• Use std::random_shuffle.
• If you have say 30 elements and only want 10, use the first 10 out the vector.

• 生成一个长度为 N 的向量并用值 1,2,...N 填充它。
• 使用std::random_shuffle。
• 如果您有 30 个元素并且只想要 10 个，请使用向量中的前 10 个。

EDIT: I have no idea how the questions are being stored, so.. :)

编辑：我不知道问题是如何存储的，所以.. :)

I am assuming the questions are being stored in a vector or somesuch with random access. Now I have generated 10 random numbers which don't repeat: 7, 4, 12, 17, 1, 13, 9, 2, 3, 10.

我假设这些问题被存储在一个向量或一些随机访问的向量中。现在我已经生成了 10 个不重复的随机数：7、4、12、17、1、13、9、2、3、10。

I would use those as indices for the vector of questions:

我会将它们用作问题向量的索引：

std::vector<std::string> questions;
//fill with questions
for(int i = 0; i < number_of_questions; i++)
{
    send_question_and_get_answer(questions[i]);
}

回答by Jon

You are trying to solve the problem "the wrong way".

您正试图以“错误的方式”解决问题。

Try this instead (supposing you have a vector<int>with question ids, but the same idea will work with whatever you have):

试试这个（假设你有一个vector<int>带有问题的 ID，但同样的想法适用于你拥有的任何东西）：

1. Get a random R from 0 to N-1 where N is the number of questions in the container
2. Add question R to another collection of "selected" questions
3. If the "selected questions" collection has enough items, you 're done
4. Remove question R from your original container (now N has decreased by 1)
5. Go to 1

1. 获取一个从 0 到 N-1 的随机 R，其中 N 是容器中的问题数
2. 将问题 R 添加到另一个“选定”问题集合中
3. 如果“选定问题”集合有足够的项目，您就完成了
4. 从原始容器中删除问题 R（现在 N 减少了 1）
5. 前往 1

回答by Max Lybbert

Sounds like you essentially want to shuffle a deck of cards(in this case, the "cards" being the questions, or question numbers).

听起来您基本上想洗一副纸牌（在这种情况下，“纸牌”是问题或问题编号）。

In C++, I would do:

在 C++ 中，我会这样做：

#include <vector>
#include <algorithms>

std::vector<int> question_numbers;
for (unsigned int i = 0; i < 10; ++i)
    question_numbers.push_back(i+1);
std::random_shuffle(question_numbers.begin(), question_numbers.end());

// now dole out the questions based on the shuffled numbers

You do not have to hand out all of the questions, any more than you have to deal out a whole deck of cards every time you play a game. You can, of course, but there's no such requirement.

您不必提出所有问题，就像每次玩游戏时都必须分发一副牌一样。你当然可以，但没有这样的要求。

回答by Benjamin Lindley

Create a vector of 10 elements (numbers 1-10), then shuffle it, with std::random_shuffle. Then just iterate through it.

创建一个包含 10 个元素（数字 1-10）的向量，然后将其打乱，使用std::random_shuffle. 然后只需遍历它。

回答by Martin York

Should look more like this: (Note: does not solve your original problem).

应该看起来更像这样：（注意：不能解决您原来的问题）。

int randomgenerator(){
  int random;

  // I know this looks re-dunand compared to %11
  // But the bottom bits of rand() are less random than the top
  // bits do you get a better distribution like this.

  random = rand() / (RAND_MAX / 11);

  return random;
}

int main()
{
    // srand() goes here.
    srand(time(0));

    while(true)
    {
        std::cout << randomgenerator() << "\n";
    }
}

A better way to solve the original problem is to pre-generate the numbers so you know that each number will appear only once. Then shuffle the order randomly.

解决原始问题的更好方法是预先生成数字，以便您知道每个数字只会出现一次。然后随机洗牌。

int main()
{
    int data[] =  { 0,1,2,3,4,5,6,7,8,9,10,11};
    int size   =  sizeof(data)/sizeof(data[0]);

    std::random_shuffle(data, data + size);

    for(int loop = 0; loop < size; ++loop)
    {
        std::cout << data[loop] << "\n";
    }
}

回答by Anthony

//non repeating random number generator
for (int derepeater = 0; derepeater < arraySize; derepeater++)
{
    for (int j = 0; j < arraySize; j++)
    {
        for (int i = arraySize; i > 0; i--)
        {
            if (Compare[j] == Compare[i] && j != i)
            {
                Compare[j] = rand() % upperlimit + 1;
            }
        }
    }
}

回答by kyriakosSt

Why not use some STL to perform the checks for you? The idea:

为什么不使用一些 STL 来为您执行检查？想法：

Create an (initially empty) setof 10 integers that will be the indices of the random questions (they will be distinct as a set forbids duplicate items). Keep pushing random numbers in [0, num_of_questions-1] in there until it grows to a size of 10 (duplicates will get rejected automatically). When you have that set ready, iterate over it and output the questions of the corresponding indexes:

创建一个（最初为空）的 10 个整数集，这些整数将作为随机问题的索引（它们将是不同的，因为一组禁止重复项）。继续将 [0, num_of_questions-1] 中的随机数推入其中，直到它增长到 10 的大小（重复项将被自动拒绝）。当您准备好该集合后，对其进行迭代并输出相应索引的问题：

std::vector<std::string> questions = /* I am assuming questions are stored in here */
std::set<int> random_indexes;

/* loop here until you get 10 distinct integers */
while (random_indexes.size() < 10) random_indexes.insert(rand() % questions.size());

for (auto index: random_indexes){
    std::cout << questions[index] <<std::endl;
}

I may be missing something, but it seems to me the answers that use shuffling of either questions or indexes perform more computations or use an unnecessary memory overhead.

我可能遗漏了一些东西，但在我看来，使用问题或索引混洗的答案会执行更多计算或使用不必要的内存开销。