Ох… впервые в этом разделе вопрос задаю, волнуюсь ))
Итак, входные данные:
Массив переменной длины, длина задается “пользователем”.
Выходные данные:
Нужно заполнить массив ранее заданной длины случайными числами из определенного диапазона. Числа не должны повторяться.
Например, длина массива задана в 50 элементов, индексы элементов массива будут с 0 до 49, заполнить нужно случайными числами из диапазона 40…160.
Собственно вопрошаю о наиболее оптимальном алгоритме.
Моё видение алгоритма:
Генерируем первое случайное число и помещаем в массив. Далее в цикле пока массив не будет заполнен (пока индекс массива меньше 50) генерируем новое случайное число и вторым циклом “пробегая” по элементам массива сравниваем с новым числом, если такого не нашлось в массиве, то добавляем его в массив, увеличиваем индекс результирующего массива и повторяем операцию.
Может быть имеется более лучший вариант алгоритма?
Либо фраза “это вполне оптимальный алгоритм” меня тоже устроит )))
Массив 0…N заполняется последовательно числами.
Затем осуществляется проход по нему, на каждом шаге генерируется случайное число R = 0…N и производится перестановка текущего элемента с элементом R.
Если я всё верно понял, то речь идет о массиве размерности N и числа в той же размерности используются?
А у меня размерность массива N, а числа из диапазона M…K
на первом проходе заполняем последовательно числами из диапазона 40…160. Получается “линейный” массив вида a[40…89] (при 50 элементах в массиве), так?
Затем идём по массиву и генерируем случайное число и заменяем его с текущим элементом массива, так? Например, a[10] был 49, а получили число 132 и вместо 49 ставим число 132, так?
Тогда я не совсем понимаю:
Каким образом неповторяемость чисел получается?
Зачем линейно заполнять массив, если потом всё равно его заменять на случайные числа?
Все верно, R[0,N] - это индекс в массиве, с которым нужно сделать перестановку текущему элементу: swap(array[i], array[R]). Два раза генерировать индексы особого смысла нет.
Ха, я сперва не понял, а потом как понял мысль @sadman41 . Да, крутяк.
Он говорит что вместо генерации случайных чисел мы случайно перемешиваем последовательные числа.
А в изначальном алгоритме при заполнении последнего элемента хз сколько раз придётся генерировать, чтобы не попасть в 49 уже имеющихся.
На время заполнения массива обявить еще один массив t, временный, размерностью K-M изначально заполнить его нулями, а при генерации случайного числа X, проверять ячейку t[K-X] если она равна нулю пишем полученное значение в массив a в ячейку t[K-X] пишем единицу, если не равна нулю генерацию случайного числа повторить.
Не стану предлагать свой вариант, просто оптимизирую авторский.
Вместо того чтоб на каждом шаге сравнивать новый элемент со всеми предыдущими, можно просто завести вспомогательный массив, где все уже выбранные числа помечать “крестиком”, тогда проверка сократится до одного действия
Вот только количество проверок для заполнения пары последних дырочек может превысить всякие разумные пределы. Вариант с равномерным заполнением, а потом перемешиванием выглядит более продуктивным.
Если для примера сократить: Размерность массива - 5, диапазон из 10…20. Как это будет выглядеть “на пальцах”?
(Ради Бога, простите мою тупость, но никак не соображу…)
Ну логично же. Берём новую колоду карт в которой карты расположены от младшей пики до старшей бубей. Далее её перетасуем любыми способами. Конечно можно набрать колоду из случайных карт собирая по всему общежитию или даже городу. Но тогда не удивляйтесь если в колоде будет двадцать тузов или королей.
В итоге задачу проще разложить на два этапа. 1-создать новую колоду, заранее программируя отсутствие некоторых карт и избегая повторов. 2-перемешиваем её как можем. Можем даже не мешать, а организовать взятие карты по случайной позиции.
Пс: я же говорил ранее, что простая последовательность псевдослучайных чисел это выстраивание чисел по возрастанию.
Ну да, если временный массив размерностью 0…K-M заполнить числами от M до K, а потом случайным образом перемешать, останется только взять из него N элементов последовательно.
В случае с последовательным заполнением заведомо большего массива есть оверхед по памяти, но остаётся предсказуемость по времени выполнения. Чего нет в варианте с перегенерацией по совпадению.
Пример:
Массив[0…9].
Числа от 50 до 99.
Вычисляем соотношение размерностей:
50…99=50; 0…9=10: 50/10=5;
Генерим случайное число(0…5), прибавляем (N*5) и прибавляем смещение 50.
Получаем почти случайные числа в порядке возрастания в диапазоне от 50 до 99.
Насколько случайны должны быть случайные числа?) В этом варианте не получить например 72 и 73. Как атомы в кристаллич. решетке, колеблются в своих “зонах”.