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

недавно делал такую штуку. Не особо заморачивался красотой и оптимизацией, надо было просто быстро сделать и все. Была написана функция bool check(byte* mas, int massize, byte chislo), которая перебирала все элементы массива mas и сравнивала их с chislo. Как только первое совпадение - возвращаем false, если их нет - true. А потом просто берем и заполняем массив случайными числами, предварительно проверяя их. То есть цикл: генерим число, делаем check, если нет такого еще - добавляем, если есть - генерим опять, пока не получится свеженькое. И так пока весь массив не заполнится. Может, не самый быстрый вариант, зато наглядно и понятно.

 

Stariy
Быдлокодерство.

 

не спорю. Но када надо реально быстро написать, пока заказчик дочитывает ТЗ до конца - такой вариант тоже сойдет.

 

Ну с таким настроением в зиродей вы еще нескоро попадете.

 

да при чем тут вообще я? Кого тут всерьез волнует моя скромная персона? Речь шла о числах...

 

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

 

собстно вот нашел в викепедии

При этом длина периода равна m тогда и только тогда, когда
1. НОД (c, m) = 1 (то есть c и m взаимно просты);
2. a - 1 кратно p для всех простых p — делителей m;
3. a - 1 кратно 4, если m кратно 4.

как теперь выразить это в числах

 

cornolio
а че так нельзя ?

Код (Text):

1. int main()
2. {
3.     unsigned int a,m,c;
4.     unsigned int i,x;
5.  
6.     m = 10;
7.  
8.     a = 41;
9.     c = 13;
10.     srand(time(NULL));
11.     x = rand(); // seed :)
12.  
13.     for(i=0;i<10;i++)
14.     {
15.         x = (a*x + c) % m;
16.         printf("%d\n",x+1);
17.     }
18.  
19.     return 0;
20. }

 

А с чего ты взял, что они не повторятся?

 

ответ дан в посте #9, причем вполне нормальное решение.

 

Как так быстро определил? Я тоже так хочу.
А зачем париться ? Можно создать битовый массив(ну или если вам охота поивращаться unsigned int) проверить и писать туда номер числа как a[g]=true: потом при генерации числа если a[g] тогда не писать и goto опять генерировать а если !a[g], то тогда писать, то есть b=g;

 

ну я понимаю что вариантов может быть не много но

 

А степень перемешивания тама зашибатая? Скажем, сколько чисел из 100 остануццо "на своих вместах" (e.g. element=i)?

 

Код (Text):

1. procedure TForm1.Button1Click(Sender: TObject);
2. const
3.  DIGITS = 16;
4. var
5.  ArrayOfDigits : array[0..DIGITS-1] of Integer;
6.  Index : Dword;
7.  RandDigit : Dword;
8.  
9. procedure DumpArray;
10. var Index : Dword;
11. begin
12.  Memo1.Lines.Add('-----------------');
13.  for Index:=0 to DIGITS-1 do
14.  begin
15.   Memo1.Text:=Memo1.Text+IntToStr(ArrayOfDigits[Index]);
16.   if Index<DIGITS-1 then Memo1.Text:=Memo1.Text+', ';
17.  end;
18.  Memo1.Text:=Memo1.Text+#13#10;
19. end;
20.  
21. begin
22.  Randomize;
23.  Memo1.Clear;
24.  ZeroMemory(@ArrayOfDigits,SizeOf(ArrayOfDigits));
25.  RandDigit:=14;
26.  DumpArray;
27.  for Index:=0 to 15 do
28.  begin
29.   ArrayOfDigits[Index]:=Index xor RandDigit;
30.  end;
31.  DumpArray;
32. end;

████████████████████████████

 

,где RandDigit число степень двойки: 14,12,8,2,4...

 

Вот! Человек на пути к ДЗЕНУ. Жму тебе руку. И код приятно читать.

 

Прикольная, кстати, биекция - из 16! в 16

 

А чем плох мой способ? Ну кроме расхода памяти? Там распределение будет очень хорошее по идее.

 

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

 

fasm, оптимизация приветствуется:

Код (Text):

1. random_seed = 0
2. macro random_byte
3. {  if random_seed
4.    else
5.      random_seed=%t
6.    end if
7.    random_seed=(random_seed-random_seed/1F31Dh*1F31Dh)*41A7h-random_seed/1F31Dh*0B14h
8.    _random_byte=(random_seed-random_seed/186A0h*186A0h) and 0FFh }
9.    
10. macro db_random_bytes db_rate
11. {  random_byte
12.    if ~ db_rate eq
13.    local rate
14.      rate=db_rate
15.      while rate
16.        db _random_byte
17.        random_byte
18.        rate=rate-1
19.      end while
20.    else
21.      db _random_byte
22.    end if }