LINUX.ORG.RU

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


0

1

Всем здравствуйте.

Нужно срочно накидать следующую программку (либо функцию).
Цель её проста:
Задается интервал случайных чисел и количество, сколько чисел нужно сгенерировать. Проблема в том, что среди сгенерированных чисел повторов быть не должно.

Разработка идет на FreePascal.

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

Буду рад помощи.

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

post-factum ★★★★★ ()

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

arsi ★★★★★ ()
Ответ на: комментарий от post-factum

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

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

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

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

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

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

Chaser_Andrey ★★★★★ ()

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

firstep ()

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

jtootf ★★★★★ ()
Ответ на: комментарий от firstep

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

post-factum ★★★★★ ()
Ответ на: комментарий от Pete_Yorn

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

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

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

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

arsi ★★★★★ ()

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

simplex ()

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

Andaril ()
Ответ на: комментарий от simplex

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

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

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

AlexVR ★★★★★ ()

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

cryptonymous ★★★ ()

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

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

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

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

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

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

ansky ★★★★★ ()

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

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

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

fool_anon ()

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

cathode ()

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

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

Pete_Yorn ()
Ответ на: комментарий от ansky

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

kt315 ()
Ответ на: комментарий от Chaser_Andrey

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

kt315 ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.