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

Приветствую!
кто силен в теории чисел подскажите какой формулой можно получить массив чилес от 1 до заданного числа, при этом чтоб были все числа и без повторов?

вот в статье
http://www.wasm.ru/article.php?article=advpoly

нашел такую формулу:

Код (Text):

1. Random(число) символизирует случайное число между 0 и число-1 (как в      
2. соответствующей C-функции)                                                
3.                                                                            
4. Encripted_Data_Size = размер зашифрованной части, округленной в сторону    
5. ближайшей степени двух (в сторону увеличения) - это я объясню позже.      
6.                                                                            
7. InitialValue = Random(Encrypted_Data_Size)                                
8.                                                                            
9.  Формула                                                                  
10.  -------                                                                  
11.       Register1 = Random(Encrypted_Data_Size)                              
12.       Register2 = InitialValue                                            
13.  Loop_Label:                                                              
14.       Decrypt [(Register1 XOR Register2)+Begin_Address_Of_Encrypted_Data]  
15.       Register1 += Random (Encrypted_Data_Size) AND -2                    
16.                                      L----->  Take care with this one!    
17.       Register1 = Register1 MOD Encrypted_Data_Size                        
18.       Register2++                                                          
19.       Register2 = Register2 MOD Encrypted_Data_Size                        
20.       if Register2!=InitialValue GOTO Loop_Label                          
21.       GOTO Begin_Address_Of_Encrypted_Data

но что то не совсем понятно с ней(

 

Код (Text):

1. for (int i = 0; i < N; i++)
2.     a[i] = i;

 

)) сори в теми не указал, что числа должны получатся в случайном порядке, то есть чтоб получалось не "123456789", а "428531796" и тп. последовательности

 

а потасовать ?

Код (Text):

1. int main()
2. {
3.     char mas[16];
4.     for (int i = 0x30; i < 0x3A; i++)
5.     mas[i-0x30] = i;
6.     mas[0xA] = 0;
7.     srand(time(NULL));    
8.     for (int i = 0; i < 1000; i++)
9.     {
10.     for (int i = 0; i < 0xA; i++)
11.     {
12.     char sim;
13.     char ofs;
14.     ofs = rand()% 0x9;
15.     sim = mas[i];
16.     mas[i] = mas[ofs];
17.     mas[ofs] = sim;
18.     }
19.     }
20.     printf(mas);
21.     return 0;
22. }

сори но я в C++ не очень

 

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

 

Можно вынимать числа в случайном порядке. В начале у нас к примеру 100 чисел, вынимаем случайный номер, стало 99, вынимаем следующее.

 

Booster
накладно. вынимка подразумевает сдвиг. те каждая вынимка == ряд чтений/записей памяти. если уж и делать так, то лучше с помощью односвязного списка, но это + 1 лишняя ссылка на элемент

 

qqwe
>накладно. вынимка подразумевает сдвиг. те каждая вынимка == ряд чтений/записей памяти.
Можно без сдвига, на место вынутого ложить последнее. Не думаю, что это должно повлиять на распределение.

 

#define N 100
void generate1(int * arr)
{
for(int i = 0;i<N;++i)
{
arr = i;
if(i>=1)
{
swap(arr[rand()%(i)],arr);
}
}
}

Почти зиродей! Не палится ни одним -авером

 

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

 

линейный конгруэнтный метод для m=10 чисел. проблема лишь в том, чтобы для конкретного m подобрать a и c. для небольших чисел это сделать несложно

Код (Text):

1. #include <stdio.h>
2. #include <stdlib.h>
3.  
4. int main()
5. {
6.     unsigned int a,m,c;
7.     unsigned int i,x;
8.  
9.     m = 10;
10.  
11.     a = 41;
12.     c = 13;
13.  
14.     x = 534205624; // seed :)
15.  
16.     for(i=0;i<10;i++)
17.     {
18.         x = (a*x + c) % m;
19.         printf("%d\n",x+1);
20.     }
21.  
22.     return 0;
23. }

 

а еще можно как-нибудь заюзать next_permutation из STL. но лучше бы LCG добить, ибо он O(m)

 

gEnIuS_99
Круто, но внесу маленькую оптимизацию. arr[0] = 0; - надо выносить до цикла.

 

Код (Text):

1. int  arr[100];
2.  
3. void FillRandom()
4. {
5. for (int i=0; i<=100; i++) {
6.      arr[i] = rand();
7. }
8. }
9.  
10. int GetRandom()
11. {
12.  int j, num;
13.  
14. while (1) {
15.      j = rand()%100    //вроде так ограничивать на 100 можно
16.      if (arr[j] != 0) {
17.           num = arr[i];
18.           arr[j] = 0;
19.           return arr[j];
20.      }
21. }

тут получается что когда останется мало итемов в массиве, то скорей всего долго будет искать. Можно тогда если 0, то сделать j++, пока не найдем не ноль. Или сохранить текущий j, и поискать по кругу

Код (Text):

1. for( int i=0; i<=100; i++) {
2.     if (arr[j] == 0) {
3.         j++;             //or j--
4.         if (j == 100)
5.            j = 0;
6.         continue;
7.     }
8.    
9.     return arr[j];
10. }
11. return NO_ITEMS_FOUND;

 

sometime
программист должен знать, что ближайшее к 100 круглое целое = 128. и, что N % 128 == N & (128 - 1)
если же вас деление не угнетает, то в качестве корня разумнее выбирать простое число

 

Или дешевый "дедовский" способ : заполняем массив 1 и как "вынули" - пишем ноль.
Естественно , если случайно попали на ноль(повторная генерация), то пропускаем.
Кстати, заодно можно проверить "случайность" генератора. Правда если он плохой, то зациклимся...
На днях проверю однако !!! Тогда и исходники будут.

 

valterg

А ещё можно то же самое делать на основе битовой карты, что в 8 раз экономнее до памяти. На Delphi можно вообще использовать set of byte, что по сути то же самое, только в красивой обёртке.

 

По идее можно использовать LFSR. При правильной выборе тапов (битов) он генерирует последовательность близкую по длине к размеру числа (те например для 16-ти битного сдвигового регистра с обратной связью он даст последовательность длиной 55000 - и повториться). Оставшиеся числа - которых должно быть мало - можно раскидать случайным образом до полной последовательности.

 

Еще как вариант два массива - один заполняется случайными числами, другой - по порядку. Потом первый сортируется, причем взаимное соответствие элементов сохраняется. Тоже, можно сказать "дедовский" способ.

 

O(nlogn)
А можно за линейное время - читайте кодес выше