массив чисел от 1 до ? в случайном порядке

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

 

gEnIuS_99

В принципе, да, но есть сомнения в равномерности распределения... хотя по идее должно быть равномерно... надо теорию думать, а мне сейчас лень, да и некогда, может через несколько дней посмотрю.
Вообще истинно правоверный матановский способ - сгенерить число в диапазоне [0, N!-1] и сконструировать соответствующую перестановку. Для N <= 12 расчеты элементарные, дальше надо оптимизить.

MEPOX

Ну это нормальный рефлекс минимально опытного человека на слово сортировка
Кстати это среднее значение, может быть и значительно хуже.

 

Ustus

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

 

А что, уже быстрее придумали?

 

gEnIuS_99
Не в том смысле, что придумали, а в том смысле, что алгоритм сортировки (при благоприятном расположении звезд, то бишь элементов в массиве) может отработать и быстрее. А может и медленнее. O(N*Log(N)) - это средняя температура по больнице. Однозначно можно сказать, что быстрее O(N) оно точно не будет.

 

gEnIuS_99,

random_seed = 0
macro random_byte
{ if random_seed ; Если random_seed сгенерен, то ессно генерить его не нуна
else
random_seed=%t ; Иначе получаем 'типа' 'timestamp_id'
end if
; Эти циферки - 'Минимальный генератор Парка-Миллера'
random_seed=(random_seed-random_seed/1F31Dh*1F31Dh)*41A7h-random_seed/1F31Dh*0B14h
_random_byte=(random_seed-random_seed/186A0h*186A0h) and 0FFh }

Стараюсь изо всех сил !

 

так-то оно всё правильно, но когда период маленький - как ни крути, числа в итоге получаются не очень качественные... закономерность прослеживается. числа будут с разницей < m. вот почему у стандартного rand() период аж 2^32 (в нем кстати тоже LCG). а когда число, полученное таким генератором, взять еще по маленькому модулю m, получается та самая желаемая псевдослучайность

поэтому надо LCG с периодом значительно больше m, плюс надо как-то контролировать его поведение, чтобы числа были уникальные. я пока не знаю как это сделать. как придумаю - расскажу

 

cornolio
т.е. тебе надо способ именно с привлечением теории чисел? а то тут и так неплохие линейные способы были представлены.

 

Вот еще один способ - RSA featured. Основано на f(x)=(x*x*x) mod n,
где n=p*q, p,q - простые.

При прохождении X периода (те n) функция дает неповторяющиеся числа в интервале [0,n-1], например для n=3*5:

При заданном числе N видимо придется искать ближайшее n>=N которое есть произведение простых (а может и не простых тоже?) и при вычислениях фильтровать на f(x)<N.

 

хм, что то не получается, вот если взять 3 и 7 то числа повторяются, если 3 и 5 то нормально

Код (Text):

1. #include "stdafx.h"
2. #include <stdio.h>
3. #include <stdlib.h>
4. #include <iostream>
5. #include <time.h>
6. int main()
7. {
8.     unsigned int i,x,b,n,m;
9.     srand(time(NULL));
10.  
11.     n =  3 * 7 ;
12.     for(b=0; b<10; b++)
13.       {
14.          x = rand()%n ; // seed
15.          for(i=0; i<n ;i++)
16.           {
17.             m = (x*x*x) % n;
18.             x++;
19.             printf("%d;", m);
20.           }
21.          printf("\n");
22.      }
23.   std::cin>>m;
24.   return 0;
25. }

 

мде опять не догнал дак еще и количество элементов в массиве должно быть переменным ? Если при m = 4,8,16,32... не очень качественная последовательность, не напрягает может тогда так попробовать.

Код (Text):

1. #define Yi 64
2. #define Yc 1
3.  
4. int main()
5. {
6.     unsigned int a,m,c;
7.     unsigned int i,x;
8.     unsigned int schet;
9.     char mas[Yi+Yc+2];
10.     srand(time(NULL));
11.     schet =0;
12. for(int z=0;z<10000;z++)
13. {
14.     m = (rand() %Yi)+Yc;
15.     a = ((rand()%Yi)+Yc)*m;
16.     a++;
17.     c = 1013904223; //большое простое число
18.  
19.     x = rand(); // seed :)
20.     if (z>9900)
21.     printf("    %d=x %d=a %d=m %d=c\n",x,a,m,c);
22.  
23.     for(i=0;i<m;i++)
24.     mas[i]=-1;
25.     for(i=0;i<m;i++)
26.     {
27.     x = (a*x + c) % m;
28.     mas[x]=0;
29.  
30.     if (z>9900)
31.     printf("%d ",x+1);
32.     }
33.     for(i=0;i<m;i++){
34.         if (mas[i]!=0){
35.         schet++;//error
36.         break;
37.         }
38.     }
39.    
40. if (z>9900)
41. printf("\n-----------------------------------------------\n");
42. }
43. printf("\n error = %d\n",schet);//распечатать число ошибок
44. system("PAUSE");
45.     return 0;
46. }

PS:сам знаю что быдлокод учу С++ по маленьку

 

cornolio

Это потому, что:

ModVal equ 3*11 ; n=p*q, exp and phi=(p-1)*(q-1) share no divisors - (3-1)*(7-1)=2*6 and 3 do share!
; but for p=3 and q=11 phi=(3-1)*(11-1)=2*10 - no common divisors

Вроде бы нету поффторений:

 

++ Кстати, метод описанный gEnIuS_99, напоминаед RC4, только тама перемешивание неравномерное (поффторяюсь).