[FreePascal] Генератор случайных чисел без повторения

После генерации каждого числа выполняется поиск числа в массиве, если оно есть — генерируется ещё раз, если нет — добавляется в массив, а счётчик количества чисел увеличивается на единицу.

какой диапазон?

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

ИМХО, лучше делать проверку, если количество чисел в промежутке не особо отличается от размера заполняемого массива, или не слишком велико тогда:

1. создаем неповторяющийся список из всех возможных вариантов.

2. Генерируем случайное число из диапазона 1..текущий_размер_списка

3. Элемент под соответственным номером заносим в массив и удаляем из списка.

4. Пока массив не заполнен - идём к шагу 2.

Предполагаемый диапозон ~ от 100 и до 1000

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

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

Хорошая идея. Можно не удалять, а заменять на -1 и делать проверку потом.

а, ерунда. тогда, имхо, самый шустрый алгоритм:

• создаём массив из n целых чисел (a[1..n], например), удовлетворяющих диапазону;
• заполняем его так, чтобы i-й элемент был равен i (a[i] = i);
• устанавливаем count = n;
• пока count > 0, делаем:
  • получить случайное число из диапазона [1..count] (обозначим его как х);
  • вывести значение ячейки a[х];
  • заменить значение a[х] = a[count];
  • уменьшить значение count на единицу.

> заменить значение a[х] = a[count];

идеологически вернее, «заменить значение a[х] = a[count], если х ≠ count;». но на практике быстрее присвоить безусловно, чем делать проверку.

А можно забить масси числами 1..1000, перемешать числа (это линейный алгоритм), и затем просто последовательно идти по массиву. Будет больше времени на подготовку, но зато быстрее «генерация»

масив булеанов, при выводе меняешь значение.

А можно забить масси числами 1..1000, перемешать числа (это линейный алгоритм), и затем просто последовательно идти по массиву. Будет больше времени на подготовку, но зато быстрее «генерация»

+1 для последовательностей до ~10^9

Если надо больше и гарантированно, то можно и Циклические группы рассмотреть.

Конструируем случайный ЛКГ максимального периода и вперед. Расход по памяти — ноль.

> среди сгенерированных чисел повторов быть не должно

Вам нужен генератор псевдослучайной цифровой последовательности.

В бумажном виде:

Искусство схемотехники: Хоровиц П., Хилл У. Том 2

Глава 9. Сопряжение цифровых и аналоговых сигналов Стр. 5

Псевдослучайные двоичные последовательности и генераторы шума Стр. 93

man Вихрь Мерсенна

А вообще задача поставленно некорректно/идиотски

Не задано нужное распределение, ничего не говорится о случайной величине (целочисленная ли она, непрерывная).

cat /dev/random ))

Берешь массив от 1 до n (или любой другой диапазон). Случайным образом генеришь число от 1 до n, пусть это будет k. Выбираешь из массива a[k] - это первое случайное число. На место a[k] записываешь a[n]. В следующей итерации генеришь случайное число от 1 до n-1, например l, выбираешь a[l] - это второе случайное число, на место a[l] записываешь a[n-1] и т.д.

Всем спасибо! Задачка решена.

Сделал массив, длинной равной интервалу чисел и выбирал случайные числа с проверкой на -1 (т.е. на место взятого случайного числа ставил -1).

Ты тред вообще читал?

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

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