Получить X уникальных номеров из набора

Question

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

В настоящий момент мне нужны случайные уникальные числа, я проверяю, не являются ли они уникальными, используя цикл while, чтобы узнать, использовал ли я случайное число раньше.

Так это выглядит так:

int n = getRandomNumber % [Array Size];

for each ( Previously used n in list)
    Check if I've used n before, if I have...try again.

Есть много способов решить эту линейную задачу O (n / 2), мне просто интересно, есть ли элегантный способ ее решения. Попытка вспомнить MATH115 «Дискретная математика» и вспомнить, рассматривал ли старый лектор что-либо, связанное с кажущейся тривиальной проблемой.

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

Answer 1

Если вы хотите, чтобы k случайных целых чисел выводилось без замены (для получения уникальных чисел) из набора {1, ..., n}, вам нужны первые k элементов в случайной перестановке [n]. Самый элегантный способ генерировать такую ​​случайную перестановку - использовать перемешивание Кнута. Смотрите здесь: http://en.wikipedia.org/wiki/Knuth_shuffle

Answer 2

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

1. Создать массив из N уникальных элементов (например, целые числа в диапазоне 0..N-1), сохранить N как arraySize и initialArraySize (arraySize = N; initialArraySize = N)
2. Когда запрашивается случайное число:
   2.1 если arraySize равен нулю, то arraySize = initialArraySize
   2.1 Создать индекс = getRandomNuber ()% arraySize
   2.3 результат = массив [индекс]. Пока не возвращать результат.
   2.2 поменять массив [index] с массивом [arraySize-1]. Своп означает «обмен» c = массив [индекс]; array [index] = array [arraySize-1]; array [arraySize-1] = c
   2.3 уменьшить arraySize на 1.
   2.4 вернуть результат.

Вы получите список случайных чисел, которые не будут повторяться, пока у вас не закончатся уникальные значения. O (1) сложность.

Answer 3

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

Таким образом, n-битный максимальный период LFSR предоставит вам последовательность (2 ^ n - 1) уникальных случайных чисел, каждое из которых имеет длину n-бит.

LFSR очень элегантный.

Answer 4

Поскольку вы навязываете уникальность, тогда должен быть достаточен генератор псевдослучайных чисел, который можно настроить так, чтобы он не повторялся столько раз, сколько вам, вероятно, нужно.Например, LCG : если для seed задано значение uint32 и изначально 0, то используйте (1664525 * seed) + 1013904223 для следующего семени и возьмите младшее слово для вашего неповторяющегося 16-битного результата.