Случайное число

[drBatty]

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

Генератор случайных чисел - это генератор случайных чисел без оговорок. Здесь писали про генератор псевдо-случайных чисел. Он генерирует последовательность чисел(жёстко заданную) которые ведут себя почти как случайные, в т.ч. могут повторятся: 123,3423,2,332,2,23,34... То, про вы писали - в общем случае очень интересная и довольно сложная задача. Но это не генератор псевдослучайных чисел.

[drBatty]

Сяшные генераторы случайных чисел -- это именно такие функции, как Ваша.

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

[promov]

Понятно, спасибо. А я считал, что Вы смеётесь, когда пишите

Случайные числа можно получить только из шума.

[Uncle_Theodore]

Сяшные генераторы случайных чисел -- это именно такие функции, как Ваша.

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

Мммм...
http://members.cox.net/srice1/random/random4.html#CRAND

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

[promov]

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

Генератор случайных чисел - это генератор случайных чисел без оговорок.

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

Вы уж растолкуйте, пожалуйста, до конца: он есть, этот генератор случайных чисел? Еcли есть, то он программа? А то из сообщений дяди Теодора cледует, что его нет, а та вещь, которая генерирует случайные числа, получает данные из вне, из шума- фактически то есть не самостоятельно генерирует, а получаемые данные преобразует в числа.
Просто-напросто из шума получать... как-то это странно. Других нет способовб, без получения данных из вне?

[drBatty]

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

Ага. А ещё зависит с чего начинать. (Хотя возможно, в ANSI генераторе всего две последовательности, а может и одна, надо проверить, я просто не помню). Насколько я понял этот документ, последовательность распадается на циклы, каждый из которых меньше m. Разве нельзя нарваться на последовательность 0 2 0 2 0 2 0 2, или как в посте выше: 9 9 9 9 9...?

[drBatty]

Вы уж растолкуйте, пожалуйста, до конца: он есть, этот генератор случайных чисел?

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

[Uncle_Theodore]

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

Ага. А ещё зависит с чего начинать. (Хотя возможно, в ANSI генераторе всего две последовательности, а может и одна, надо проверить, я просто не помню). Насколько я понял этот документ, последовательность распадается на циклы, каждый из которых меньше m. Разве нельзя нарваться на последовательность 0 2 0 2 0 2 0 2, или как в посте выше: 9 9 9 9 9...?

В принципе, можно добиться того, чтобы линейный конгруэнтный генератор выдавал m разных чисел.
Посмотрите тут:
http://www.answers.com/topic/linear-congruential-generator

Вы уж растолкуйте, пожалуйста, до конца: он есть, этот генератор случайных чисел?

Нет и быть не может. То о чём пишет Uncle_Theodore не относится к программированию.

Почему не относится? Разве чтение /dev/random -- не программистская задача?
Если Вы имеете в виду, что алгоритмически невозможно изготовить полностью случайные числа, тогда да...

[promov]

Вы уж растолкуйте, пожалуйста, до конца: он есть, этот генератор случайных чисел?

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

Ясно, пока вопросов нет, спасибо.

[drBatty]

Разве нельзя нарваться на последовательность 0 2 0 2 0 2 0 2, или как в посте выше: 9 9 9 9 9...?

В принципе, можно добиться того, чтобы линейный конгруэнтный генератор выдавал m разных чисел.
Посмотрите тут:
http://www.answers.com/topic/linear-congruential-generator

ну зачем так далеко ходить, в #21 посте я уже привёл пример такого генератора(сам придумал, но использовал при этом такую же литературу, как автор статьи). Кроме того, насколько я помню(могу и ошибиться), там период не m, а m-1. Хотя я и не отыскал этого хитрого числа.

Нет и быть не может. То о чём пишет Uncle_Theodore не относится к программированию.

Почему не относится? Разве чтение /dev/random -- не программистская задача?
Если Вы имеете в виду, что алгоритмически невозможно изготовить полностью случайные числа, тогда да...

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

[edranovdenis]

\dev\random разьве не стык условно замкнутых, детерменированных систем? рулетка-таймер крутиться, а мышь, клава и сеть тыкают в эту рулетку пальцем через драйвер. если возникает необходимость использовать urandom значит не удовлетворяется условие ассинхронности по времени.
коллапс волновой функции штука занимательная, но тут не в тему...

[nikita Moroz]

Господа, у меня обратная задача: получить 20000 псевдослучайных чисел от 1 до 20000 но так, что-бы числа не повторялись. Нужно в реальной задаче. Это не философская задача!. Чем лучше воспользоваться? Каким алгоритмом?

[Zeus]

Получается что нужно в произвольной последовательности выдать числа от 1 до 20000 - и чем дальше, тем более предсказуемым будет следующий член последовательности, т.к. повторения недопустимы.
Совсем уж "псевдо" получается.

[edranovdenis]

int k=20000,a[k],n,m=1;
for(n=k;n>0;n--){a[n]=m++;}
for(n=k;n>0;n--){int r=rand()%k;m=a[r];a[r]=a[n];a[n]=m;}

извиняйте за оформление, пишу с телефона

[edranovdenis]

в алгоритме есть ошибочка :)
ее найти надо прежде чем использовать в реальной задаче...

[drBatty]

получить 20000 псевдослучайных чисел от 1 до 20000 но так, что-бы числа не повторялись.

Используйте массив в 20000 char'ов например так:

Код: Выделить всё

#define N 20000

static char m[N];

void init_rand()
{
 int j;
 for(j = 0; j < N; j++) m[j] = 0;
}

int rand_other()
{
 int x;
 while(m[x = rand() % N]);
 m[x] = 1;
 return x;
}

Тут ещё два замечания:
1) Вместо rand() используйте более лучшей реализацией(например из #21 поста)
2) При попытке генерации 20001 числа программа зависнет.

PS: Если N очень большое, используйте битовые карты(к примеру, если N около 4 000 000, битовая карта займёт около 500килобайтов). Если N ещё больше, воспользуйтесь хешированием, Отобразите свои числа в N^ВЅ хешей. Например для 2^32 чисел, используйте хеш длинной 16 бит.

[Uncle_Theodore]

drBatty, по поводу 21го поста. Насколько я понимаю, там описан стандартный конгруэнтный генератор псевдослучайных чисел. (На таких и rand() основан тоже). Единственное что, когда Вы пишете mod 32 -- Вы имеете в виду остаток от деления на 32, так? Каким же образом Вы собираетесь сгенерить число между нулем и 2^{32}-1?
Или это какая-то другая операция?

[drBatty]

Единственное что, когда Вы пишете mod 32 -- Вы имеете в виду остаток от деления на 32, так? Каким же образом Вы собираетесь сгенерить число между нулем и 2^{32}-1?
Или это какая-то другая операция?

Прошу прощения, имелась ввиду операция взятия остатка по модулю 2^32(4 294 967 296).

PS: Я отредактировал это сообщение.

[edranovdenis]

drBatty, вы предлагаете стрелять рандом в битовую карту и отмечать места попадания 1-й? количество холостых будет расти и теоретически такой алгоритм может работать бесконечно долго. можете запустить цикл с рандом до 4млн и подождать пока ранд попадет в 45378 например...

[Uncle_Theodore]

drBatty, вы предлагаете стрелять рандом в битовую карту и отмечать места попадания 1-й? количество холостых будет расти и теоретически такой алгоритм может работать бесконечно долго. можете запустить цикл с рандом до 4млн и подождать пока ранд попадет в 45378 например...

Поскольку у Вас кольчество слуяайных чисел равно длине интервала, откуда они берутся, Вам стоит посмотреть на random permutation algorithms. В Гугле много про это есть. Вот, навскидку.
http://www2.toki.or.id/book/AlgDesignManua...OK4/NODE151.HTM
http://www.techuser.net/randpermgen.html

[drBatty]

drBatty, вы предлагаете стрелять рандом в битовую карту и отмечать места попадания 1-й? количество холостых будет расти и теоретически такой алгоритм может работать бесконечно долго. можете запустить цикл с рандом до 4млн и подождать пока ранд попадет в 45378 например...

Наоборот, я предлагаю стрелять пока не попадёт в то, что уже было. В примере рандом был с периодом 4 миллиарда, а диапазон всего 20000. Проверка не очень и нужна, совпадений почти никогда не будет(только в самом конце, последнее число сгенерируется за 10000 попыток в среднем). Если нужен более быстродействующий алгоритм(и если надо генерить именно 20000 чисел, а не 100-200, как я предполагал), то мой можно модифицировать например так: Если осталось всего n значений из N возможных, необходимо сгенерировать число от 0 до n, например k, а затем взять k-ое число из множества N(точнее подмножества N(n)). Реализация нужна? Я просто не знаю, для какой цели нужны эти 20000 чисел.

[drBatty]

http://www.techuser.net/randpermgen.html

Ну да, я делал что-то подобное, однако брал двоичное дерево. В результате получались неповторяющиеся числа от 0 до 2^N.

[edranovdenis]

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

[drBatty]

с английским туго. можно на пальцах показать?

Да что тут показывать? Спускаемся по дереву в случайном порядке(если rand()&1 == 1, вправо, иначе влево), если узел уже был - переходим на следующий, если вернулись обратно - всё, все числа уже были. Ну ещё можно отрывать у дерева листики, по мере генерации чисел, тогда с каждым числом дерево становится меньше. Что-то вроде:

Код: Выделить всё

struct tree_node
{
 tree_node *left;
 tree_node *right;
};

int tree_rand()
{
 if(!root)  return -1;//всё дерево обошли, чисел больше нет.
 int r = 0;
 tree_node *cur = root;
 tree_node *pc = &root;
 while(cur->left || cur->right)
 {
   if(cur->right && cur->left)
     pc = rand()&1 ? &(cur->right) : &(cur->left);
   else if(cur->right)
     pc = &cur->right;
   else
     pc = &cur->left;
  r *= 2;
  r += (*pc == cur->right);
  cur = *pc;
 }
 *pc = NULL;
 delete cur;
 return r;
}

Что-то вроде этого... Ессно для генерации N чисел нужна память для 4*N указателей.

ЗЫ правда там немного не то с вероятностями получится: Например при N=4
1шаг: {1/4;1/4;1/4;1/4}
2шаг: {1/2;1/4;1/4}
3шаг: {1/2;1/2}
4шаг: {1}
На втором шаге вероятности немного не те, должно быть {1/3;1/3;1/3}, но мне на тот момент именно это и было нужно, а уж как это модифицировать - решайте сами

[drBatty]

ЗЫ правда там немного не то с вероятностями получится

Ну и не лень мне такой бред было писать...
Всё ведь совсем по другому было: Мне нужно было быстро сгенерировать N не повторяющихся случайных чисел, причём равновероятных, и при N около 2^20. Вроде лотереи 6 из 36.

Опишу кратко, может кому пригодится.
1) Сначала я создал бинарное красно-чёрное дерево из N узлов.
2) Для поиска числа, я вычислял случайное(или псевдослучайное) число x, от 0 до n, где n количество оставшихся на данный момент чисел(тех которых ещё не было).
3) Искал в дереве х-овое число(в центрированном порядке обхода)
4) Удалял это число из дерева
5) И возвращал случайное число соответствующее диапазону 0...N.

Для поиска в дереве узла по номеру я использовал вес узла, равный сумме весов поддеревьев +1. При этом вес корня равен числу узлов(полезно для п2), также возможно быстро(O(log(n)) найти узел №n.

Для п5, я просто сразу выделил массив из N узлов(для N==2^20 получилось 12Mb), и впоследствии просто вычитал из указателя на узел указатель на начало массива.

Ну а про остальное(red-black tree и т.д.) всё уже подробно написано у Кнута(п2.3)