Блог

Как указано в названии, я пытаюсь создать уникальную последовательность случайных чисел каждый раз, когда запускаю эту маленькую программу.

Однако иногда я получаю такие результаты, как:

 102
201
102
  

Код

 #include <cstdlib>
#include <ctime>
#include <iostream>

using namespace std;

int main() {
        for (int i = 0; i < 3; i  ) {
                srand (time(NULL) i);
                cout << rand() % 3;
                cout << rand() % 3;
                cout << rand() % 3 << 'n' << endl;
        }
}
  

Очевидно, что srand не обладает той волшебной функциональностью, которую я хотел. Я надеюсь, что вокруг этого есть логический взлом?

Редактирование 1: Чтобы уточнить, это всего лишь простая тестовая программа для того, что будет реализовано в большем масштабе. Таким образом, вместо 3 итераций rand%3 я мог бы выполнить 1000 или более randP. Если я увижу 102 в какой-то момент его работы, я бы хотел, чтобы я никогда больше не видел 102.

Прежде всего, если бы вы собирались использовать srand / rand , вы бы хотели использовать его один раз (и только один раз) в начале каждого выполнения программы:

 int main() {
    srand(time(NULL));
    for (int i = 0; i < 3; i  ) {
    cout << rand() % 3;
    cout << rand() % 3;
    cout << rand() % 3 << 'n' << endl;
}
  

Во-вторых, time обычно результат выдается только с разрешением в одну секунду, поэтому даже с этой поправкой, если вы запустите программу дважды за одну секунду, вы можете ожидать, что она выдаст идентичные результаты в двух запусках.

В-третьих, вы все равно не хотите использовать srand / rand . Генератор случайных чисел в <random> целом значительно лучше (и, что, возможно, более важно, достаточно лучше определен, чтобы представлять гораздо более известную величину).

 #include <random>
#include <iostream>

int main() { 
    std::mt19937_64 gen { std::random_device()() };
    std::uniform_int_distribution<int> d(0, 2);

    for (int i = 0; i < 3; i  ) {
        for (int j=0; j<3; j  )
            std::cout << d(gen);
        std::cout << "n";
    }
}
  

Однако, основываясь на редактировании, этого все еще недостаточно. Что вам действительно нужно, так это случайная выборка без дублирования. Чтобы получить это, вам нужно сделать больше, чем просто генерировать числа. Случайно сгенерированные числа не только могут повторяться, но и неизбежно будут повторяться, если вы сгенерируете их достаточное количество (но вероятность повторения становится довольно высокой, даже если это еще не неизбежно).

Пока количество результатов, которые вы создаете, невелико по сравнению с количеством возможных результатов, вы можете довольно легко просто сохранять результаты в наборе по мере их создания и обрабатывать результат как фактический результат, только если он ранее не присутствовал в наборе:

 #include <random>
#include <iostream>
#include <set>
#include <iomanip>

int main() {
    std::mt19937_64 gen { std::random_device()() };
    std::uniform_int_distribution<int> d(0, 999);
    std::set<int> results;

    for (int i = 0; i < 50;) {
        int result = d(gen);
        if (results.insert(result).second) {
            std::cout << std::setw(5) << resu<
              i;
            if (i % 10 == 0)
                std::cout << "n";
        }
    }
}
  

Это становится весьма неэффективным, если количество результатов приближается к количеству возможных результатов. Например, давайте предположим, что вы производите числа от 1 до 1000 (таким образом, 1000 возможных результатов). Подумайте, что произойдет, если вы решите выдать 1000 результатов (т. Е. Все возможные результаты). В этом случае, когда вы создаете последний результат, на самом деле остается только одна возможность — но вместо того, чтобы просто создавать эту одну возможность, вы создаете одно случайное число за другим за другим, пока не наткнетесь на единственную оставшуюся возможность.

Для такого случая есть лучшие способы выполнить эту работу. Например, вы можете начать с контейнера, содержащего все возможные числа. Чтобы сгенерировать выходные данные, вы генерируете случайный индекс в этом контейнере. Вы выводите это число и удаляете это число из контейнера, затем повторяете (но на этот раз контейнер на единицу меньше, поэтому вы уменьшаете диапазон вашего случайного индекса на единицу). Таким образом, каждое случайное число, которое вы создаете, дает один результат.

То же самое можно сделать, просто перетасовав массив чисел. Однако у этого есть два недостатка. Во-первых, вам нужно правильно их перетасовать — перетасовка Фишера-Йейтса работает хорошо, но в противном случае легко вызвать смещение. Во-вторых, если вы на самом деле не используете все (или очень близко ко всем) числа в массиве, это неэффективно.

В крайнем случае рассмотрите возможность использования нескольких (например, 10) 64-разрядных чисел. В этом случае вы начинаете с заполнения массива числами от 2 ^64-1. Затем вы выполняете 2 ^замены 64-2. Итак, вы выполняете примерно 2 ⁶⁵ операций только для получения 10 чисел. В этом крайнем случае проблема должна быть совершенно очевидной. Хотя это менее очевидно, если вы создаете (скажем) 1000 чисел по 32 бита за штуку, у вас все равно есть та же основная проблема, только в несколько меньшей степени. Итак, хотя это допустимый способ сделать что-то для нескольких конкретных случаев, его применимость довольно узкая.

Сгенерируйте массив, содержащий 27 трехзначных чисел, цифры которых меньше 3. Перетасуйте его. Перебирайте перетасованный массив по мере необходимости, значения будут уникальными, пока вы не исчерпаете их все.

Как указывали другие люди, не продолжайте заполнять ваш генератор случайных чисел. Кроме того, rand это ужасный генератор, вы должны использовать один из лучших вариантов, доступных в стандартных библиотеках C .

Вы эффективно генерируете трехзначное базовое число 3. Используйте выбранный вами ГСЧ, чтобы сгенерировать базовое число 10 в диапазоне 0 .. 26 и преобразовать его в базовое число 3. Это дает 000 .. 222.

Если вам абсолютно необходимо избегать повторений, затем перетасуйте массив, как предлагает pjs. Это приведет к тому, что более поздние числа будут «менее случайными», чем более ранние числа, потому что они взяты из меньшего пула.