Генератор псевдослучайных чисел...

← →
ArtemESC © (2006-08-26 19:58) [0]

Есть какой-то входной параметр и некоторое число n...
Есть ли какой-нибудь алгоритм Random(n), генерирующий число n в зависимости от входного параметра и изменяющий входной параметр для дальнейшего использования:
1) Через некоторое количество проходов входной параметр станет равен первоначальному, но при этом за все шаги между ними функцией Random будет сгенерированы все числа n, хотя бы один раз (желательно с равномерным распределением - то есть все числа выпадут одинаковое число раз)
2)Числа на выходе будут достаточно перемешанны (для человеческого взгляда)

← →
ArtemESC © (2006-08-26 20:01) [1]

>> все числа n
все числа от одного до n...

← →
Мефисто (2006-08-26 20:04) [2]

ПО для автоматов-лохотронов?

Книги Дональда Кнута, или Джулиана Бакнелла к примеру.

Или поиск по инету: Рандомизированные алгоритмы.

← →
Ketmar © (2006-08-26 20:06) [3]

есть.

← →
БарЛог © (2006-08-26 20:08) [4]

Я тоже думал о таком алгоритме, но выходило все криво и очень долго :)
Подходит для проигрывания песен в случайном порядке (например в винампе, но там он их повторяет за один проход :( ).
Тоже буду рад послушать мысли.

← →
DrPass © (2006-08-26 20:08) [5]

> 1) Через некоторое количество проходов входной параметр
> станет равен первоначальному, но при этом за все шаги между
> ними функцией Random будет сгенерированы все числа n, хотя
> бы один раз (желательно с равномерным распределением - то
> есть все числа выпадут одинаковое число раз)

Нет, потому что это уже не будет равномерным распределением. Любая "гарантия" выпадания числа уже ломает весь принцип случайности. Но ты можешь сам сделать такой "полуслучайный" алгоритм. Для этого понадобится массив 1..n, функция random и немножно фантазии.
> 2)Числа на выходе будут достаточно перемешанны (для человеческого
> взгляда)

Критерий перемешанности?

← →
ArtemESC © (2006-08-26 20:09) [6]

Мефисто (26.08.06 20:04) [2]
Мне нужно сейчас, а Толмуды осваивать в данный момент некогда...

← →
DprYg © (2006-08-26 20:10) [7]

Можешь где-нибудь скачать Фундаментальные алгоритмы и структуры данных в Delphi Бакнелла - там это есть.

← →
ArtemESC © (2006-08-26 20:13) [8]

>> DrPass © (26.08.06 20:08) [5]
немножно фантазии - опасно, ибо может оказаться, что некоторые числа не при каких условиях не могут выпасть...

← →
Мефисто (2006-08-26 20:16) [9]

http://materials.diasoft.kiev.ua/alg_delphi/alg_delphi.zip

← →
ArtemESC © (2006-08-26 20:18) [10]

>> DrPass © (26.08.06 20:08) [5]

>>Критерий перемешанности?
Ну скажемъ, расстояние между соседними генерациями не меньше некоторого x...

← →
default © (2006-08-26 20:32) [11]

опиши сабж по-русски
случайную перестановку чисел от 1 до n надо что-ли? (1)
"хотя бы один раз"
можно выполнить (1), а потом Random(n)+1 покуда нужно

← →
ArtemESC © (2006-08-26 20:34) [12]

default © (26.08.06 20:32) [11]
Нет,
ты не понял я хочу написать Random, со свойствами в [0]...

← →
default © (2006-08-26 20:41) [13]

как я понял, например, для n=5 и числа элементов = 8
надо получить случайную последовательность в которой есть числа 1,2,3,4,5 и ещё 3(8-5) числа из того же множества
для этого можно выделить массив из 13 элементов, заполненного так:
1,2,3,4,5,Random(n)+1,Random(n+1),Random(n+1) и далее случайно перемешать числа в массиве желательно линейным алгоритмом

оно?

чтобы я понял надо писать понятно
а то как пишем так и думаем поэтому ничего самостоятельно и не получается...

← →
palva © (2006-08-26 20:47) [14]

Только будет генерировать все числа от 0 до n-1.
Нужно выбрать какое-нибудь число m взаимно простое с n.

Если k очередное число, то следующее число k будет

k * m mod n

Число m должно быть не очень маленьким, чтобы результат выглядел перемешанным, скажем больше 5, а еще лучше взять число близкое к n. Но тут нужно не переборщить, чтобы не переполнилась разрядная сетка при переполнении.

← →
palva © (2006-08-26 20:48) [15]

чтобы не переполнилась разрядная сетка при умножении.

← →
Дураг (2006-08-26 22:24) [16]

http://algolist.manual.ru/maths/generator/index.php

← →
ArtemESC © (2006-08-26 23:56) [17]

default © (26.08.06 20:41) [13]
Извени, но я теперь, вообще ничего не понял...

palva © (26.08.06 20:47) [14]
Объясни подробнее, пожалуйста...

← →
default © (2006-08-26 23:59) [18]

ArtemESC © (26.08.06 23:56) [17]
можешь рассказать в связи с какой задачей сабж поднят?

← →
Ketmar © (2006-08-27 00:01) [19]

вообще -- стандартная задача о перемешивании колоды карт. %-)

← →
ArtemESC © (2006-08-27 00:15) [20]

Ketmar © (27.08.06 00:01) [19],
нет никаких колод и карт...

default © (26.08.06 23:59) [18]
Генератор, основой генерирования которого будет число, которое я буду сохранять после использования (оно меняется), чтобы в дальнейшем использовать в этой процедуре (вообще говоря, верхняя граница генерирования будет постоянна), через некоторое количество раз это число станет первоночальным - надо подобрать такой алгоритм, чтобы за все шаги генерации выпали все числа меньшие верхней границы. При этом, желательно приблизительно одинаковое количество раз...

← →
default © (2006-08-27 00:29) [21]

ArtemESC © (27.08.06 00:15) [20]
количество раз за которое мы приходим к исходному значению параметра равно "верхняя граница генерирования "+"какая-то величина"
вот хотелось бы узнать о "какая-то величина" ?
что о ней можно сказать? она ограничена? можно её приравнять к нулю для всех значений параметра? искомый алгоритм при нескольких вызовах с одним и тем же значением параметра должен выдавать одну и туже последовательность? как меняется параметр после вызова генератора? и зачем?

← →
Zeqfreed © (2006-08-27 00:35) [22]

Задачу я конечно не на 100% понял. Вот код, что в его работе не устраивает? :)

unit Unit2; interface uses Windows; const DEFAULT_ARRAY_SIZE = 25; type TRandomizer = class FNumbers : array of Integer; FUpperBoundary : Integer; public constructor Create(); overload; constructor Create(const Size, Seed : Integer); overload; procedure Reset(const Size, Seed : Integer); function Generate() : Integer; end; implementation { TRandomizer } constructor TRandomizer.Create; begin inherited Create(); Reset(DEFAULT_ARRAY_SIZE, GetTickCount); end; constructor TRandomizer.Create(const Size, Seed: Integer); begin inherited Create(); Reset(Size, Seed); end; function TRandomizer.Generate() : Integer; var r : Integer; begin r := Random(FUpperBoundary); Result := FNumbers[r]; FNumbers[r] := FNumbers[FUpperBoundary]; FNumbers[FUpperBoundary] := Result; Dec(FUpperBoundary); if (FUpperBoundary < 0) then FUpperBoundary := High(FNumbers); end; procedure TRandomizer.Reset(const Size, Seed: Integer); var i : Integer; begin RandSeed := Seed; SetLength(FNumbers, Size); for i := 0 to Size - 1 do begin FNumbers[i] := i; end; FUpperBoundary := Size - 1; end; end.

← →
Ketmar © (2006-08-27 00:35) [23]

> [20] ArtemESC © (27.08.06 00:15)
намекаю ещё раз: стандартная задача о перемешивании колоды карт.
если что, могу и в третий раз повторить. %-)

← →
ArtemESC © (2006-08-27 00:39) [24]

default © (27.08.06 00:29) [21]
>> количество раз за которое мы приходим к исходному значению
>>параметра равно "верхняя граница генерирования "+"какая-то величина"
>>вот хотелось бы узнать о "какая-то величина" ?
Верхняя граница - это n в привычном нам Random(n)

Вот псевдокод псевдоалгоритма:
Load(Param)
Number := GenerateNumber(n, Param)
Param := GenerateParam(n, Param)
Save(Param)

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

← →
Zeqfreed © (2006-08-27 00:46) [25]

> [24] ArtemESC © (27.08.06 00:39)

А для чего планируется использовать этот Param?

← →
Zeqfreed © (2006-08-27 00:51) [26]

Если я правильно понял, то Param нужен для того, чтобы сохранять состояние генератора и при необходимости возвратиться к тому же самому состоянию, при котором будут генерироваться те же самые последовательности. Тогда в моем коде можно сохранять сам массив чисел на произвольном шаге и исходный RandSeed, этого будет достаточно.

← →
ArtemESC © (2006-08-27 00:53) [27]

Zeqfreed © (27.08.06 00:35) [22]
Упс, из-за того, что я не могу толком объяснить задачу, страдают люди...

Zeqfreed © (27.08.06 00:46) [25]
Random - я пишу сам (саммммм!!!), (и вообще говоря мне это нужно на ассемблере - но это не важно), а Param - нужен в качестве генерирующего материала...

← →
Zeqfreed © (2006-08-27 00:55) [28]

> [27] ArtemESC © (27.08.06 00:53)

> Упс, из-за того, что я не могу толком объяснить задачу,
> страдают люди...

Наоборот, люди не страдают фигней, а пишут код :)

> Random - я пишу сам (саммммм!!!),

Похвально, но орать незачем, ага?

ArtemESC © (27.08.06 00:53) [27]
так ёлки какая-то определённость с числом шагов за которые параметр должен вернуться к исходному значению есть?

вот представь, n=3, Param=5 и:
Load(5)
GenerateNumber(n, 5) = 2;
GenerateParam(n, 5) = 4;
Save(4);
GenerateNumber(n, 4) = 1;
GenerateParam(n, 4) = 3;
Save(3);
GenerateNumber(n, 3) = 0;
GenerateParam(n, 3) = 5;
Save(5);
останавливаемся, Param=5; все числа от 0 до n-1 получены
если теперь стартовать с n=3 и Param=4, то условие "все числа от 0 до n-1 получены" выполнено не будет

default © (27.08.06 01:08) [31]
>>если теперь стартовать с n=3 и Param=4, то условие "все числа от 0 до n-1 >>получены" выполнено не будет

Ну так я хочу подобрать такие процедуры GenerateNumber и GenerateParam чтобы были выполнены все условия....

ArtemESC © (27.08.06 01:11) [32]
например, для n=5 будем рассматривать такие циклы значений параметров:(пусть значения параметра - натуральные числа)
1 2 3 4 5 (за значением параметра "5" идёт значение параметра "1")
6 7 8 9 10
11 12 13 14 15
...
таким образом, для каждого значения параметра определено следующее за ним значение и каждое значение параметра достигает самого себя за 5 шагов чего достаточно, чтобы за цикл поиметь все числа от 0..n-1
каждому циклу можно поставить по некоторому правила перестановку чисел 0..n-1
если для первого цикла это перестановка: 0,2,3,1,4
то для Param=1 получим, 0,2,3,1,4
для Param=2: 2,3,1,4,0
для Param=3: 3,1,4,0,2
и тд
такое пойдёт?

Ketmar © (27.08.06 00:35) [23]
Берем массив A[1..n], A[1]:=1, A[2]:=2, ... , A[n]:=n;
Перемешиваем числа в массиве. Идем for-ом по массиву, получаем нужную последовательность. После завершения цикла массив можно заново перемешать. Оно?

default © (27.08.06 01:35) [34]
БарЛог © (27.08.06 10:06) [35]
Да не о том речь (вообще!!!!! не о том!!!!), последовательность возникает в дискретном смысле,
то есть генерируется число (и теоретически!!! это число являеться членом некоторой последовательности) генератором - я его использую, косвенно генерируеться и новый параметр и сохраняеться, через некоторое количество раз (может даже компьютер будет несколько раз выключен и включен, параметр то сохранен) параметр становиться первоночальным (цикл), и я его использую, как сначала (и в течении цикла возникает эта своего рода последовательность со свойствами в [0])...

← →
SergP. (2006-08-27 21:17) [39]

Помниться когда-то давно (в эпоху калькуляторов) я юзал такой "генератор" псевдослучайных чисел для генерации последовательности чисел x в диапазоне от 0 до 1:

x := дробная часть (11*х + Pi)

Но генератора где можно было бы управлять периодом я не знаю

SergP. (27.08.06 21:17) [39]
Как периодом управлять??

Опять меня не понимают

Генератор псевдослучайных чисел... Найти похожие ветки