Как удостовериться, что случайным образом сгенерированные числа не повторяются? [дубликат]

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

Например:

HashSet<int> array = new HashSet<int>();
            array.Add(1);
            array.Add(2);
            array.Add(1);
            foreach (var item in array)
            {
                Console.WriteLine(item);
            }
            Console.ReadKey();

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

Подход с сохранением всех сгенерированных чисел довольно быстро замедлит вычисления; чем больше у вас номеров, тем больше вам потребуется хранилища, пока вы не заполните всю доступную память. Лучшим методом было бы (как кто-то уже предлагал) использовать хорошо известный генератор псевдослучайных чисел, такой как Linear Congruential Generator ; он супербыстрый, требует только модульного умножения и сложения, а теория, лежащая в его основе, часто упоминается в Vol. 2 из TAOCP Кнута. Таким образом, задействованная теория гарантирует довольно большой период перед повторением, и единственное необходимое хранилище - это используемые параметры и начальное число.

Вот интересное решение, которое я придумал:

Предположим, у вас есть числа от 1 до 1000 - и у вас недостаточно памяти.

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

Вы можете разделить массив на две части, так что у вас будет массив из 1-500 и один пустой массив

Затем вы можете проверить, существует ли число в массиве 1 или не существует во втором массиве.

Предполагая, что у вас есть 1000 чисел, вы можете получить случайное число от 1 до 1000. Если его меньше 500, проверьте массив 1 и удалите его, если он есть. Если его НЕТ в массиве 2, вы можете добавить его.

Это вдвое снижает использование памяти.

Если вы распространяете это с помощью рекурсии, вы можете разделить массив 500 на 250 и пустой массив.

Предполагая, что пустые массивы не используют места, вы можете немного уменьшить использование памяти.

Поиск также будет значительно быстрее, потому что, если вы разбиваете его много, вы генерируете число, например 29. Оно меньше 500, меньше 250, меньше 125, меньше 62, меньше 31, больше чем 15, поэтому вы выполняете эти 6 вычислений, а затем проверяете массив, содержащий в среднем 16/2 элемента - всего 8.

Я должен запатентовать этот поиск, хотя я уверен, что он уже существует!

Не существует чистого функционального подхода, который не является O(n^2) по количеству возвращенных результатов - каждый раз, когда генерируется число, вам нужно проверять каждый результат. Кроме того, подумайте о том, что происходит, когда вы возвращаете, например, 1000-е число из 1000 - вам потребуется в среднем 1000 попыток, пока случайный алгоритм не придумает последнее неиспользованное число, причем каждая попытка потребует в среднем 499,5 сравнений с уже сгенерированными числами.

Из этого должно быть ясно, что ваше описание в том виде, в котором оно было опубликовано, не совсем то, что вы хотите. Лучший подход, как уже говорили другие, это взять список, например, из 1000 чисел, перемешать его, а затем возвращать числа из этого списка постепенно. Это гарантирует, что вы не вернете ни одного дубликата, и вернет числа за время O(1) после первоначальной настройки.

Если они не могут быть повторены, они не случайны.

РЕДАКТИРОВАТЬ:

Более того ...

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

Вы можете хранить числа в векторе и получать их по индексу (1..n-1). После каждой случайной генерации удалите индексированное число из вектора, затем сгенерируйте следующее число в интервале 1..n-2. и т. д.

unsigned int N = 1000;
vector <unsigned int> vals(N);
for(unsigned int i = 0; i < vals.size(); ++i)
   vals[i] = i;
std::random_shuffle(vals.begin(), vals.end());

unsigned int random_number_1 = vals[0];
unsigned int random_number_2 = vals[1];
unsigned int random_number_3 = vals[2];
//etc

Существует класс генераторов псевдослучайных чисел, который, как я полагаю, обладает желаемыми свойствами: Линейный конгруэнтный генератор . Если он определен правильно, он создаст список целых чисел от 0 до N-1, без двух повторяющихся чисел, пока вы не используете все числа в списке один раз.

#include <stdint.h>

/*
 * Choose these values as follows:
 *
 * The MODULUS and INCREMENT must be relatively prime.
 * The MULTIPLIER-1 must be divisible by all prime factors of the MODULUS.
 * The MULTIPLIER-1 must be divisible by 4, if the MODULUS is divisible by 4.
 *
 * In addition, modulus must be <= 2**32 (0x0000000100000000ULL).
 *
 * A small example would be 8, 5, 3.
 * A larger example would be 256, 129, 251.
 * A useful example would be 0x0000000100000000ULL, 1664525, 1013904223.
 */

#define MODULUS    (0x0000000100000000ULL)
#define MULTIPLIER (1664525)
#define INCREMENT  (1013904223)

static uint64_t seed;

uint32_t lcg( void ) {
    uint64_t temp;

    temp = seed * MULTIPLIER + INCREMENT;   // 64-bit intermediate product
    seed = temp % MODULUS;                  // 32-bit end-result

    return (uint32_t) seed;
}

Все, что вам нужно сделать, это выбрать МОДУЛЬ, чтобы он был больше, чем количество чисел, которые вам понадобятся в данном прогоне.

Если вы используете простой 32-битный линейный конгруэнтный ГСЧ (например, так называемый «Минимальный стандарт» ), все, что вам нужно сделать, это сохранить начальное значение, которое вы используете, и сравнить каждое сгенерированное число. к нему. Если вы когда-нибудь снова достигнете этого значения, ваша последовательность начнет повторяться, и вы потеряете значения. Это O (1), но, конечно, ограничено 2 ^ 32-1 значениями (хотя я полагаю, вы также можете использовать 64-битную версию).

Я думаю, что есть 3 возможных подхода, в зависимости от размера диапазона и требуемой производительности, вы можете использовать другой алгоритм.

1. Создайте случайное число, посмотрите, есть ли оно в (отсортированном) списке. Если не добавить и не вернуть, иначе попробуйте другой.
   • Ваш список будет расти и потреблять память с каждым числом, которое вам нужно. Если каждое число 32-битное, оно будет каждый раз увеличиваться как минимум на 32 бита.
   • Каждое новое случайное число увеличивает коэффициент попадания, и это замедляет его.
   • O (n ^ 2) - я думаю
2. Создать битовый массив для каждого числа в диапазоне. Отметьте как 1 / True, если он уже возвращен.
   • Каждое число теперь занимает только 1 бит, это может быть проблемой, если диапазон большой, но теперь каждое число выделяет только 1 бит.
   • Каждое новое случайное число увеличивает коэффициент попадания, и это замедляет его.
   • O (n * 2)
3. Предварительно заполнить список всеми числами, перемешать его и вернуть N-е число.
   • Список не будет расти, возвращаемые числа не будут замедляться
   • , но создание списка может занять много времени и много памяти.
   • O (1)

В зависимости от необходимой скорости вы можете хранить все списки в базе данных. Они не должны находиться в памяти, кроме скорости.

Заполните список нужными числами, затем перемешайте список и выберите свои числа с одного конца.

Сколько случайных чисел вам нужно? Может быть, вы можете применить алгоритм перемешивания к предварительно вычисленному массиву случайных чисел?

Если у вас нет проблем, когда значение может быть вычислено по предыдущему, то LFSR и LCG подойдут. Когда вы не хотите, чтобы одно выходное значение могло быть вычислено другим, вы можете использовать блочный шифр в режиме счетчика для генерации выходной последовательности, учитывая, что длина блока шифра равна длине выхода.

Предположим, size=100.000, затем создадим массив с таким размером. Создайте случайные числа, а затем поместите их в массив. Проблема в том, каким индексом будет это число? randomNumber%size даст вам индекс.

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

Например, для последних разделов 1231232444556 3458923444556

у вас никогда не будет таких номеров в вашем списке, даже если они совершенно разные, но последние разделы одинаковы.

Вы можете выделить достаточно памяти для массива бит с 1 битом для каждого возможного числа. и проверять / устанавливать биты для каждого сгенерированного числа. например, для чисел от 0 до 65535 вам понадобится всего 8192 (8кб) памяти.

Особенно учитывая желаемое количество значений, вам нужен линейный регистр сдвига обратной связи.

Почему?

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

Оказывается, в статье Википедии есть несколько примеров кода C++, которые более проверены, чем все, что я бы дал вам из головы. Обратите внимание, что вы захотите ищать значения из циклов - циклы просто итерируют регистр сдвига. Вы можете увидеть это в фрагменте здесь.

(Да, я знаю, что это было упомянуто, кратко в обмане...видел его, когда пересматривал. Учитывая, что он не был поднят здесь и является лучшим способом решить вопрос плаката, я думаю, что его следует поднять снова.)

Генератор случайных чисел не может выдавать значения, зависящие от ранее выведенных значений, потому что они не будут случайными. Однако вы можете повысить производительность, используя разные пулы случайных значений, каждый со значениями, объединенными разным значением соли, которое разделит количество проверяемых чисел на количество пулов, которые у вас есть.

Если диапазон случайных чисел не имеет значения, вы можете использовать действительно большой диапазон случайных чисел и надеяться, что вы не получите никаких коллизий. Если ваш диапазон в миллиарды раз больше, чем количество элементов, которые вы ожидаете создать, ваши шансы на столкновение невелики, но все же есть. Если числа не имеют фактического случайного распределения, у вас может быть двухчастный номер {счетчик} {случайные числа x}, который обеспечит уникальный номер, но не будет случайным образом распределен.

Это не будет случайным, если есть такая закономерность?

Насколько я знаю, вам придется хранить и фильтровать все нежелательные номера...