рандомный генератор не повторяющихся чисел

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

 

на васме уже поднималась эта тема. Поищи. Но чего-то похожего на решение я не помню. Хотя какие-то формулы там давались

 

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

чёрт с 60% , увеличу допустимый диапазон, пусть хоть 5% будет, но гарантированно

 

Гарантию дает только страховый полис... А так

Код (Text):

1. for (ii = 0; ii < MAX_VALUE; ++ii)
2. {
3.    RndVal = Hash(ii);
4. }

Для MD5 вероятность коллизии 1 / (2^64). Для чисел небольшой разрядности неплохие результаты показывает Hsieh Hash (h**p://w*w.azillionmonkeys.com/qed/hash.html). Если не нравится простой цикл - поставьте MT (h**p://en.wikipedia.org/wiki/Mersenne_twister)

 

поищи по словам "перестановки", "размещение"
http://wasm.ru/forum/viewtopic.php?id=26149
http://wasm.ru/forum/viewtopic.php?pid=351130#p351130

 

MSoft gazlan
огромное спасибо!

MSoft
добавления лучше отдельным постом делать, а не правкой.
а то в списке новых сообщений не видно

 

да флудить не хотелось

 

Генераторы, у которых период равен 2^32 или 2^32-1, то есть простейшие конгруэнтный или crc-гамма дают числа во всем диапазоне ни разу не повторяясь, пока не пробегут всевозможные значения, в чем вопрос?

 

вопрос в случайности. Если вызвать этот генератор несколько раз, будут ли 2 ряда чисел отличаться?

 

persicum
в том чтоб свести к некратному диапазону.

 

Тоже не понимаю смысла задачи. Ввести глобальную переменную, содержащую опорный Seed. Иначе всегда будет вероятность повторения, ибо опорное значение рандомно.

 

Взять последовательность 1,2,3... (считаем что все числа - 64бит)
и зашифровать блочным шифром с размером блока 64 и рандомным ключом.

 

ага, теперь немного понятно. Разумеется, генераторы с периодом 2^32 будут повторятся после пробега по всему пространству - давать ту же самую последовательность.

Значит можно взять те же простейшие быстрейшие генераторы, но с периодом 2^64, которые имеют SEED 64 бит. Их проекции на 32 бит тогда НЕ БУДУТ ПОВТОРЯТСЯ.

 

persicum
Если есть 2^64 РАЗНЫХ чисел и 32-бита из них не будут повторяться?
Это сомнительно. Скорее, они повторятся, но в псевдо-случайном порядке.

 

Праильна, вот зашел чтобы поправится =)))
Если нужны неповторяющиеся числа, но повторяющаяся периодичность, бери период 2^32
Если нужена именно неповторяющаяся последовательность, но возможны повторения отдельных чисел, то бери 64 бит генератор и младшие 32 бит.

А чтобы угодить и тем и другим построй конгруентный генератор с периодом 2^48, тогда разделив его выдачу на 2^48 получишь неповторяющиеся вещественные с периодом 2^48 - очень большой период, можно считать что устроит. А если совсем круто, то делай генератор с периодом 2^52 или чтобы не было нуля 2^52-1, сувай в double - и период будет офигенным и ни одно число не будет повторяться.

 

Нужно особенно подчеркнуть, что хороший вещественный генератор теоретически невозможен на базе вещественной математики. Хороший вещественный генератор возможен только на базе дискретной математики. Поэтому смотри, скока целых бит вмещается в double - 52 бита мантисса. Поэтому нужно построить целочисленный генератор именно на 52 бита и разделить его выдачу на 2^52.

 

тут есть 2е проблемы.
рандомный генератор будет давать повторяющиеся числа.
генератор последовательностей предсказуем при повторном пробеге (#13).

в первом случае можно чекать по таблице (32 число - 16м таб)
во втором бежать по последовательности с неким некратным шагом. шаг выбирать в 0 позиции поледовательности произвольно. для упрощения саму длину последовательности можно выбрать простой

можно еще их собирать вручную из 2х-3х случайных целых.

 

Существует множество "плохих" генераторов которые дают в пределах модуля (N) непересекающиеся петли. Например:

Xi+1=((Xi ror A) mul B) mod N.

При задании разных X0 они образуют множества (петли) внутри N, причем эти петли не пересекаются.

Единственная проблема - нужно помнить номер "петли" (внутри функции или вызывющий). Возможно как-то можно аналитически получить элемент не принадлежащий к данной петле = func(A,B,Xi).

 

MSoft

qqwe

Насколько я понимаю, сама задача #1 предусматривает только один пробег (просто получение очередного квазислучайного числа, отличного от всех предыдущих). Если так, то достаточно взять генератор последовательности нужной длины и "просто" запоминать его состояние, чтобы при последующих вызовах генерить последовательность дальше

 

Пытался переосмыслить правила построения конгруэнтного генератора применительно к 2^n.

x = ( a x + b) mod 2^n, достаточно взять b нечетное и чтобы (a-1) делилось на 4. Так?