Генерация случайного ряда без повторов.

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

Код (Text):

1. randomize;  
2.  
3.       FOR i:=0 to NN-1 do a_flag[i]:=True;  //инициализация массива флажков
4.       FOR i:=0 to NN-1 do begin
5.           tmp:=random(NN);                  //
6.           j:=i;
7.           WHILE True do begin
8.              if a_flag[tmp]then begin       // если место "не занято"
9.                a_goal[j]:=tmp;                // то вставляем случайное число
10.                a_flag[tmp]:=False;          // и "занимаем место"
11.                break;
12.                end;
13.              tmp:=tmp+1;        // если место "занято", то переходим к cледующему
14.                                        //??? а насколько вот это решение "уничтожает" случайность ????
15.              
16.               if tmp=NN then tmp:=0;   // если при переходе доходим до границы до уходим в начало диапазона.
17.              end;
18.       end;

На выходе получаем a_goal какой нам надо.
Но надо это получать раз в 5 быстрее. А лучше в 10 Есть более быстрый алгоритм?

Спасибо большое.

 

создать упорядоченный массив всех нужных значений и перемешать его.

 

или так

Код (Text):

1. //LastNum - максимальное число из диапазона
2. //FirstNum - мин-ое число из диапазона
3. int Array1[n];
4. int Array2[n];
5. int x = LastNum - FirstNum;
6. int tmp;
7.     for (int i = 0; i < n; i++)
8.         {
9.         Array1[i] = FirstNum + i;
10.         }
11.     for (int i = 0; i < n; i++)
12.         {
13.                        if (!x) x = 1;
14.         tmp = Random()%x;
15.         Array2[i] = Array1[tmp];
16.         Array1[tmp] = Array1[x];
17.         x--;       
18.         }

Правда последние оставшиеся 2 числа извлекуться в заранее известном порядке

 

Д. Кнут. "Искусство программирования". Том 2. Алгоритм 3.4.2P. Для перестановки элементов {0,...,NN-1} на паскале это выглядит примерно так:

Код (Text):

1. randomize;
2. for i:=0 to NN-1 do
3. begin
4.   tmp:=Random(i+1);
5.   a_goal[i]:=a_goal[tmp];
6.   a_goal[tmp]:=i;
7. end;

В предположении равновероятности и независимости результатов Random все возможные перестановки получаются
с одной и той же вероятностью (равной, как нетрудно догадаться, 1/NN!).

 

http://www.wasm.ru/forum/viewtopic.php?pid=189777#p189777

 

А насколько случаен должен быть ряд вообще? Если достаточно просто нормального распределения, то достаточно следующего алгоритма:
Ni=((N(i-1)*X+Y) xor Z) mod NN
X - взаимно простое с NN, Y,Z - любое
подобрать числа для хорошего распределения можно эксперементальным путем в зависимости от NN.

 

Большое спасибо всем. Сначала у меня некоторое сомнение вызвал вариант предложенный diamond, но потом понял, что он мне подходит...
Единственный вопрос, есть реализация гсч для дельфи быстрее чем стандартный дельфийский random?

 

можешь попробовать формулу

x := a * x + b
b = 2 * m + 1
a = 4 * n + 1

m и n - какие-нить целые числа.

 

В частности, если a=5 и b=1,
то получается такой быстрый код

lea eax,[eax+eax*4]
inc eax

должно по теории пробегать все 2^32 значений, включая ноль.

 

persicum Это T-function. Это ни под каким микроскопом не случайно и даже не псевдослучайно. И это вообще не по теме.

/me может только вздыхать...

HN2008 Держись как можно дальше от таких "генераторов". А перемешивать легко, как это в RC4 сделано – asd правильно написал. Надо только random быстрый...

 

Бред...