(no subject)

[beldmit]

Последними дискуссиями у Витуса навеяло.

Я очень хорошо помню этот момент. Год был 1992-й, я только поступил в институт. Мы с Лешей Студеновым собирались писать на Pascal-е (C я тогда не знал) некую экономическую игру. Договорились вечером, разошлись по домам, и я задумался.

Игра начиналась с раздачи карт. Карты естественным образом ложились в двумерный массив, а раздавать надо было датчиком случайных чисел. И тут я задумался - а что, если одна и та же карта выпадет в раздаче дважды? Немного подумав, я понял, что просто повторять раздачу этой карты бесполезно - то же число может выпасть и третий раз. Мне стало очень грустно. И тут меня осенило - есть же цикл while! Он решит все проблемы!

Второго такого озарения с тех пор в моем програмистском опыте не было. Но ощущения я запомнил навсегда.

Comments

[vitus_wagner]

Есть другой способ - при выдаче каждой следующей карты генерировать случайное число на единицу меньше.
Правда, тогда цикл понадобится для того чтобы найти карту номер N, не считая уже выданых. Но зато время завершения детерминировано.
Этот способ более точно имитирует раздачу карт из колоды. Хотя еще более точной имитацией было бы сгенерировать случайную перестановку массива, а потом просто отсчитать N первых.

[slobin.livejournal.com]

less /usr/lib/python2.5/random.py
/def sample

Узнаешь много нового и интересного (например, она пользуется двумя разными алгоритмами в зависимости от соотношения размеров колоды и выборки).

... За каникулами, книгами и кеннингами канувших князей ...

[beldmit.livejournal.com]

Теоретически они должны быть эквивалентны. Но двумерным массивом доя меня тогда оперировать было естественнее.

[city-rat.livejournal.com]

Эмммм... Вот так и погибает программирование, как искусство, превращаясь из математической игры в подбор подходящей языковой конструкции... Вместо учебников - доки и спеки.

Вообще-то можно просто закодить формулу, который по заданному [псевд]случайному семечку возвращает псевдослучайную последовательность заведомо неповторяющихся чисел, причем в нужном диапазоне. У Кнута, скажем, спереть - у него целый том этому посвящен, помнится.

Кинуть кубик еще раз, кстати, плохой метод, порождает уязвимости.

[beldmit.livejournal.com]

Оно не может оставаться искусством при таком количестве практикующих.

Фамилию Кнута я тогда не слышал еще.

[city-rat.livejournal.com]

О, нашел. Тридцатисекундный поиск по "последовательность неповторяющихся псевдослучайных чисел кнут"

Вопрос: хочу получить последовательность чисел от 0 до N-1, в случайном порядке, причём они не должны повторяться.

Ответ:
x(n+1) = (a * x(n) + c) % N, x(0) = rand(),

где a взаимно просто с N;
a - 1 кратно p для всех простых p — делителей m;
a - 1 кратно 4, если m кратно 4.

Выдаёт числа от 0 до N-1 в псевдослучайном порядке.

Это называется линейным конгруэнтным генератором (linear congruential generator, LCG). Существует множество других генераторов. Подробности во втором томе Кнута.

[vitus_wagner]

Аплодисменты!

[beldmit.livejournal.com]

Браво!

[arilou]

Или я не понял, или у тебя опечатка? где в формуле 'm' и есть ли какие-либо условия на 'c'?

[city-rat.livejournal.com]

Я скат-н-пейстил не вчитываясь, просто для примера. Первоисточник там указан, если кому надо - найдет.

[gegmopo4.livejournal.com]

Проще занести все карты в колоду (массив), а при выборе менять случайную карту местами с верхней и снимать с верха колоды.