Детеминированный рандом?

[mikhailk]

Есть потребность в многократном получении одной и той же последовательности псевдослучайных чисел, равномерно распределенных по диапазону. Скажем, от 1 до 100. При этом должно быть несколько вариантов этой последовательности, скажем, тоже штук 100.

По идее, генератор должен инициализироваться каким-то значением и потом при запросе чисел выдавать одну и ту же последовательность. При этом, при инициализации разными начальными параметрами, последовательности должны получаться разные. Может кто видел готовое решение?

ЗЫ. Была идея сделать совсем тупо - нагенерить массив из 1000 случайных чисел и потом просто брать фрагменты этого массива, но может есть простое математическое решение?

ЗЗЫ. Линейно-конгруэнтный метод я уже попробовал. Не понравилось.

[Aquahawk]

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

[mikhailk]

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

[Wolsh]

Так Вам не случайность нужна вообще, а перемешивание.

[ChuwY]

Все-таки хотелось бы услышать более точную формулировку задачи.
Поисковый запрос "random seed actionscript" выдает кучу вариантов.
Под рукой пока, увы, нет.

[mikhailk]

Более точная формулировка задачи выглядит так:


// нужен некоторый класс RandomDt, который выдает случайные числа в диапазоне от 0
// до некоторого лимита (напр., 10) в зависимости от некоторого параметра (напр., 1234567 ),
// который указывается при инициализации: RandomDt.init( 10, 1234567 )

var rand1 : Array() = [];
var rand2 : Array() = [];
var rand3 : Array() = [];
var i : int;

// серия 1
RandomDt.init( 10, 1234567 );
for ( i = 0; i < 1000; i++ ) {
rand1.push( RandomDt.getValue() );
}

// серия 2
RandomDt.init( 10, 987654 );
for ( i = 0; i < 1000; i++ ) {
rand2.push( RandomDt.getValue() );
}

// серия 3
RandomDt.init( 10, 1234567 );
for ( i = 0; i < 1000; i++ ) {
rand3.push( RandomDt.getValue() );
}

// по итогам испытаний должно получиться:
// - rand1 эквивалентен rand3
// - rand2 отличается от rand1, rand3
// - rand1, rand2, rand3 запонены числами от 0 до 9, при
// этом все числа встречаются с примерно равной
// частотой

[alexcon314]

Заполнить массив из 1000 элементов пачками [0...9], тогда числа будут присутствовать в (примерно) равной пропорции, и перемешать получившийся массив по какому-то алгоритму с параметром, имитирующему случайность перемешивания. Перемешивая массив просто случайным образом не добиться п.1. За алгоритм сейчас не скажу, думать надо :).
Например, можно в пачках [0...9] перед заполнением задавать определенный порядок чисел (таких вариантов будет 10! = 3628800, если я ничего не путаю), а заполнять и перемешивать большой массив уже каким-то статическим алгоритмом (без параметра). Можно попробовать за основу взять битмап дату 1х1000 и что-то мутить с пиксельной информацией, сид как-то привязать к цвету...

[mikhailk]

Заполнить массив из 1000 элементов

Это я в самом начале написал.
И, видимо, так и сделаю.

Единственно, не совсем понятно, почему все время всплывает тема с перемешиванием. Вот как работает штатный Math.random():


var rands:Array = [];
var count:int = 1000;

for ( var i:int = 0; i < count; i++ ) {
var randIndex:int = int( Math.random() * 10 );
rands[randIndex] = int( rands[randIndex] ) + 1;
}

for ( var j:int = 0; j < 10; j++ ) {
trace( j, '=>', Math.floor( rands[j] / ( count / 1000 ) ) / 10, '%' );
}


выдает:


0 => 10.8 %
1 => 9.8 %
2 => 8.3 %
3 => 8.2 %
4 => 10.3 %
5 => 11.8 %
6 => 9.2 %
7 => 9 %
8 => 10.3 %
9 => 12.3 %


Т.е., очевидно, что разброс есть, но при увеличении числа испытаний он будет нивелироваться. Мне нужно то же самое, только с возможностью начальной инициализации.

[alexcon314]

Вы же потребовали, чтобы был параметр инициализации, условно говоря "сид", обеспечивающий уникальность и воспроизводимость набора.
Вы не сможете удовлетворить этому требованию, если заполнять массив через random(). Не получится на 100% воспроизвести результат предыдущего заполнения. Или вы как-то иначе себе это представляете?
Почему перемешивание? Потому что ваша задача по-сути комбинаторная, а не статистическая. Перемешивание - суть перестановка заранее известного неизменяемого набора элементов. По крайней мере, формулировка задачи наводит именно на такой подход.
Немного раскрою свою мысль, если вы не поняли. Пачку [0...9] можно перед добавлением в массив из 1000 зараннее перемешать, одним из известных вам спосбов, назовем условно это "паттерном заполнения". Добавляем последовательно пачки в массив. Потом, 1000 элементов нужно переставить по какому-то однозначному и обратимому алгоритму, типа как это делается в случае со случайным перемешиванием, но только без рандома :). Ну, переставим местами чет-нечет и потом пройдемся по каждой пачке реверсом со смещением на 3 .. или еще как-то..насколько фантазии хватит.
На выходе должен получится массив из все тех же чисел, встречающихся в равной пропорции и в порядке, прямо зависящем от способа первоначального перемешивания пачки [0...9]. Т.е. удовлетворяем условиям: "непохожесть" выхлопа для двух разных паттернов заполнения и обеспечиваем воспроизводимость выхлопа при одинаковых паттернах. Ну, и внешне такой выхлоп вряд ли сильно будет отличаться от результата рандомного заполнения :). При таком подходе имеем 10! возможных вариантов выхлопов.

Написал, и как-то вспомнилось про криптографию. Может в эту сторону посмотреть?

[Aquahawk]

Ваш же код выполнен 1000 000 итераций и убрал транкейт в результате
0 => 10.0518 %
1 => 10.005799999999999 %
2 => 9.960099999999999 %
3 => 10.0067 %
4 => 10.0224 %
5 => 9.9896 %
6 => 10.0302 %
7 => 9.975000000000001 %
8 => 9.997 %
9 => 9.9614 %

вы хотите на 1000 итераций на 10 групп получить абсолютно равномерное распределение и при этом хотите чтобы это был рандом? чего-то вы не того хотите.

[Zebestov]

Пардон за "ленивый порт" — выдрал этот рандомайзер из текущего проекта на javascript. Но суть ясна.

var rands:Array = [];
var count:int = 1000;

function seededRandom(max:Number = 1, min:Number = 0):Number
{
seed = (seed * 9301 + 49297) % 233280;
var rnd:Number = seed / 233280;
return min + rnd * (max - min);
}

// Указываем какой-то определенный seed
var seed:int = 333;

for ( var i:int = 0; i < count; i++ ) {
var randIndex:int = int( seededRandom(10, 0) );
rands[randIndex] = int( rands[randIndex] ) + 1;
}

for ( var j:int = 0; j < 10; j++ ) {
trace( j, '=>', Math.floor( rands[j] / ( count / 1000 ) ) / 10, '%' );
}

Конкретно этот код выдает такое распределение:

0 => 10.7 %
1 => 8.9 %
2 => 8.8 %
3 => 10.5 %
4 => 9.2 %
5 => 10.8 %
6 => 10.7 %
7 => 10 %
8 => 11.1 %
9 => 9.3 %

[mikhailk]

вы хотите на 1000 итераций на 10 групп получить абсолютно равномерное распределение и при этом хотите чтобы это был рандом? чего-то вы не того хотите.

не-не, не абсолютно
я же написал "примерно":


// - rand1, rand2, rand3 запонены числами от 0 до 9, при
// этом все числа встречаются с примерно равной
// частотой


результат работы стандартной функции рандом я привел просто для примера, что такрй вариаент мнея вполне устраивает.


Почему перемешивание? Потому что ваша задача по-сути комбинаторная, а не статистическая. Перемешивание - суть перестановка заранее известного неизменяемого набора элементов. По крайней мере, формулировка задачи наводит именно на такой подход.

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

Добавлено через 1 минуту
Пардон за "ленивый порт" — выдрал этот рандомайзер из текущего проекта на javascript. Но суть ясна.


О, супер.
То, что и было нужно.

[Aquahawk]

а то что это линейный конгурентный вас не смущает?

[mikhailk]

а то что это линейный конгурентный вас не смущает?

А вот в этом случае почему-то нет. :)