Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.191.174.168] |
|
Сообщ.
#1
,
|
|
|
Здравствуйте!
Подскажите, пожалуйста, как заполнить массив случайными, не повторяющимися числами? |
Сообщ.
#2
,
|
|
|
Я делаю так:
1. Для i=1..N : a[i] = i; 2. Для i=1..N : a[i] обмен с a[random(N)]. |
Сообщ.
#3
,
|
|
|
Я бы только сделал так:
2. Для i=1..N-1 : a[i] обмен с a[i + 1 + random(N - i)]. |
Сообщ.
#4
,
|
|
|
Увы, но так нельзя, Profi!
Ибо: а) на первое место никогда не будет поставлен элемент №1 - потеря равномерности/независимости (частное высказывание); б) (общее) на первых местах чаще будут элементы с большими номерами - потеря равномерности/независимости. |
Сообщ.
#5
,
|
|
|
Цитата Славян @ Увы, но так нельзя, Profi! Ибо: а) на первое место никогда не будет поставлен элемент №1 - потеря равномерности/независимости (частное высказывание); б) (общее) на первых местах чаще будут элементы с большими номерами - потеря равномерности/независимости. a) А это ли не цель? б) Неа. Конечно очень мало вероятна, но может быть ситуация когда последний элемент встанет на первое место, а остальные просто сдвинуться на шаг вперед. Если интересно, почитай про Knuth shuffle. |
Сообщ.
#6
,
|
|
|
Цитата Profi @ Непонятен вопрос. Весьма размыт. Но вариант когда на первом месте никогда не будет элемента №1 внушает сомнение в случайности. a) А это ли не цель? |
Сообщ.
#7
,
|
|
|
Цитата Славян @ Цитата Profi @ Непонятен вопрос. Весьма размыт. Но вариант когда на первом месте никогда не будет элемента №1 внушает сомнение в случайности.a) А это ли не цель? Ну, в целом согласен. С другой стороны, есть вероятность (хоть и опять же минимальная), что Random будет каждый раз выдавать значение i и в результате будет обычный массив с элементами по индексу. |
Сообщ.
#8
,
|
|
|
Сбацал маленький тест (пардон, что на Си, но не суть, думается):
#include <iostream> #include <stdio.h> #include <stdlib.h> #define n 1000 int main(int,char**) { //std::cout << "Hello World!\n"; int *a = new int[n]; double itog[2]={0,0}; for( int r=0; r<1000; r++) { srand(r); for( int i=0; i<n; i++) a[i] = i; for( int i=0; i<n; i++) std::swap( a[i], a[rand()%n]); // Славян //for( int i=0; i<n-1; i++) std::swap( a[i], a[i+1+(rand()%(n-1-i))]); // Profi long long l1 = 0, l2 = 0; for( int i=0; i<n/2; i++) l1 += a[i], l2 += a[i+n/2]; printf("1) %g\t2)%g\n", l1*0.002, l2*0.002); itog[0] += l1*0.002, itog[1] += l2*0.002; } printf("A) %g\tB)%g\n", itog[0]*0.001, itog[1]*0.001); return 0; } Славян: A) 484.941 B) 514.059 Profi: A) 498.919 B) 500.081 Ничего не понимаю , но метод Profi однозначно лучше! Надо думать... |
Сообщ.
#9
,
|
|
|
Хотелось бы уточнить условие, оно противоречиво - случайные числа на то и случайны, что могут и повториться, "случайными, не повторяющимися" - в некотором роде противоречие.
Не указан диапазон значений чисел, их тип. Известен ли заранее размер массива? Просто, возможны варианты, например, если заранее известен размер массива N, и это степень двойки, а "случайные" числа - целые от 0 до N-1, то возможен совсем простой и эффективный вариант: 1. Генерируем всего одно случайное число C в пределах от 0 до N-1. 2. Заполняем массив числами i Xor C, где i - индекс в массиве. |
Сообщ.
#10
,
|
|
|
По классике это делается через запись цифр от 0 до N-1 по очереди, в случайное свободное поле, где случайное число является смещением от последнего заполненного.
Ну что-то наподобие вот такого program MakeRandArray; {$APPTYPE CONSOLE} {$R *.res} function MakeArray(ACount: Integer): TArray<Integer>; var I, CurPos, RandOffset: Integer; begin // инициализация SetLength(Result, ACount); for I := 0 to ACount - 1 do Result[I] := -1; CurPos := -1; // бежим по массиву пока есть не заполненые элементы while ACount > 0 do begin // генерируем случайное смещение RandOffset := Random(ACount) + 1; // сдвигаемся вправо от текущей позиции на RandOffset НЕЗАПОЛННЕНЫХ элементов массива while RandOffset > 0 do begin Inc(CurPos); if CurPos = Length(Result) then CurPos := 0; // контролируем выход за диапазон if Result[CurPos] < 0 then Dec(RandOffset); end; // заполняем выбранную позицию Result[CurPos] := ACount - 1; Dec(ACount); end; end; procedure PrintArray(Value: TArray<Integer>); var I: Integer; begin Write(Value[0]); for I := 1 to Length(Value) - 1 do Write(', ', Value[I]); Writeln; end; var AArray: TArray<Integer>; begin Randomize; AArray := MakeArray(10); PrintArray(AArray); Readln; end. Добавлено Ну а саму генерацию массива можно немного модифицировать используя усилитель рандома через сложение для генерации гарантированно уникального числа function MakeArray(ACount: Integer): TArray<Integer>; const MaxRandStep = 30; var I, CurPos, RandOffset, RandValue: Integer; begin // инициализация RandValue := Random(MaxRandStep); SetLength(Result, ACount); for I := 0 to ACount - 1 do Result[I] := -1; CurPos := -1; // бежим по массиву пока есть не заполненые элементы while ACount > 0 do begin // генерируем случайное смещение RandOffset := Random(ACount) + 1; // сдвигаемся вправо от текущей позиции на RandOffset НЕЗАПОЛННЕНЫХ элементов массива while RandOffset > 0 do begin Inc(CurPos); if CurPos = Length(Result) then CurPos := 0; // контролируем выход за диапазон if Result[CurPos] < 0 then Dec(RandOffset); end; // генерируем гарантированно случайное число Inc(RandValue, Random(MaxRandStep) + 1); // заполняем выбранную позицию Result[CurPos] := RandValue; Dec(ACount); end; end; |
Сообщ.
#11
,
|
|
|
Цитата Rouse_ @ По классике это делается через запись цифр от 0 до N-1 по очереди, в случайное свободное поле, где случайное число является смещением от последнего заполненного. То, что я написал, на порядок производительнее, и даёт тот же результат. |
Сообщ.
#12
,
|
|
|
Цитата Mikle @ То, что я написал, на порядок производительнее, и даёт тот же результат. С таким же успехом можно было бы заполнить массив Arr[I] := I Это не случайные числа, это возрастающие последовательности от опорного Допустим на рандоме 100 это будет ряд 100, 101, 102, 103 etc... Ну а с учетом что диапазон рандома указан в пределах 0..N-1, то при рандомном нуле будет вообще красиво |
Сообщ.
#13
,
|
|
|
Ну мой вариант это решение из Кнута насколько я помню, классика ж говорю, только там помоему не сдвиг был а просто выбор случайного в диапазон (0..количество не заполненных) было
Конечно это не O(N) но рандом нормальный выйдет |
Сообщ.
#14
,
|
|
|
Цитата Rouse_ @ это будет ряд 100, 101, 102, 103 etc... а "etc..." будет "96, 97, 98, 99, 108, 109..." Естественно, не очень то рэндом получается. Я же написал: "Хотелось бы уточнить условие". А мой пример был не совсем удачной демонстрацией, что такую задачу можно выполнить за O(N). Если подумать, как задачу "заполнить массив, каждый раз подставляя случайное по порядку из оставшихся неиспользованными чисел" выполнить за O(N), то получится: N чисел в случайном порядке можно расставить N! способами (это не нужно пояснять?). Тогда генерируем одно случайное число от 0 до N!-1 - оно будет однозначно идентифицировать порядок расстановки всех чисел. Осталось найти способ из числа восстановить эту последовательность - вот это будет красивое решение задачи. Правда, для небольших последовательностей - факториал быстро растёт. И, да, существует вероятность выпадения нуля, но эта вероятность будет равна вероятности выпадения последовательно "0, 1, 2,.. N-1" при "классическом" решении. Добавлено Цитата Rouse_ @ Конечно это не O(N) но рандом нормальный выйдет По качеству - да, всё в порядке. Я там выше написал с ошибкой, и, почему-то, не получалось отредактировать своё сообщение. Я удалил и написал новое. |
Сообщ.
#15
,
|
|
|
Цитата Rouse_ @ Где он указан?Ну а с учетом что диапазон рандома указан в пределах 0..N-1 Цитата DDim1000 @ Подскажите, пожалуйста, как заполнить массив случайными, не повторяющимися числами? Вы решаете не ту задачу как по мне. |
Сообщ.
#16
,
|
|
|
Цитата cppasm @ Где он указан? Текст не читаем чтоли? Цитата Mikle @ 1. Генерируем всего одно случайное число C в пределах от 0 до N-1. |
Сообщ.
#17
,
|
|
|
Цитата Rouse_ @ Текст не читаем чтоли? Так вот как раз и вижу что не читаете. Это не автор темы если что. У вас для массива из двух элементов всегда будет { 0, 1 } либо { 1, 0 } Почему не { 150, 39 } ? |
Сообщ.
#18
,
|
|
|
Цитата cppasm @ У вас для массива из двух элементов всегда будет { 0, 1 } либо { 1, 0 } У кого у нас? В моем варианте не будет Прикреплённый файлMakeRandArray.zip (29,84 Кбайт, скачиваний: 37) |
Сообщ.
#19
,
|
|
|
Цитата Rouse_ @ У кого у нас? У тебя в первом варианте тоже. Во втором (который позже добавил) - нет. |
Сообщ.
#20
,
|
|
|
Цитата cppasm @ У тебя в первом варианте тоже. Во втором (который позже добавил) - нет. Ну потому что это два разных алгоритма, первый рандомная расстановка, второе усиление на базе рандомной расстановки, нес-па? |
Сообщ.
#21
,
|
|
|
Мне одному кажется, что в данной теме "афтор" замешан лишь косвенно. И тема живёт сама по себе.)
|
Сообщ.
#22
,
|
|
|
Цитата RusSun @ И тема живёт сама по себе.) Хорошие темы должны жить! У меня одна тема есть - живет уже 10 лет http://forum.delphimaster.net/cgi-bin/foru...1430155755&p=67 |
Сообщ.
#23
,
|
|
|
Цитата Rouse_ @ Хорошие темы должны жить! +1000 У MicroSoft тоже есть одна великолепная тема - живет с 1987г. Дай б-г ей долголетия на миллионы лет |