Перемешать массив чисел | |
---|---|
Extortioner Сообщений: 854 Откуда: Новосибирск Дата регистрации: 06.10.2005 |
Добрый день, давайте попробуем решить такую задачку:
Дан массив чисел, от 1 до n пусть n будет достаточно большим. Необходимо перемешать этот массив случайным образом. Мне удалось на своём не самом быстром компьютере добиться значения 1,656 сек для n = 500 000 Естественно вывод не учитываем - проверяем правильность работы процедуры на малых n. Ну и небольшое дополнение для любителей простых решений (ведь можно сказать, что если мы поменяем просто два элемента массива местами то массив перемешан ) - каждый элемент массива должен поменять своё местоположение. Ну или хотя бы сделать попытку к изменению Исправлено 3 раз(а). Последнее : Extortioner, 19.04.11 14:15 |
Re: Перемешать массив чисел | |
---|---|
Goodwin Сообщений: 3539 Откуда: Омск Дата регистрации: 03.05.2006 |
А каков критерий случайности?
Если я массив в обратном порядке или сначала чёт/потом нечёт выведу проканает? ------------------ Что мы знаем о лисе? Ничего. И то не все. (С)Б. Заходер |
Re: Перемешать массив чисел | |
---|---|
katana Сообщений: 20 Дата регистрации: 17.01.2011 |
Пробный шар (т.к. не совсем понял условие)
n=500000 DECLARE mas[n] FOR i=1 TO n mas[i]=INT(RAND()*500000) ENDFOR pol=INT(n/2) ?mas[1],mas[pol+1],mas[2],mas[pol+2] &&..etc j=SECONDS() FOR i=1 TO pol mas[i]=BITXOR(mas[i],mas[i+pol]) mas[i+pol]=BITXOR(mas[i+pol],mas[i]) mas[i]=BITXOR(mas[i],mas[i+pol]) ENDFOR ?SECONDS()-j ?mas[1],mas[pol+1],mas[2],mas[pol+2] &&...etc |
Re: Перемешать массив чисел | |
---|---|
Extortioner Сообщений: 854 Откуда: Новосибирск Дата регистрации: 06.10.2005 |
Не, ну каждый раз мы должны получать разные наборы чисел на выходе - то есть не должно быть какого-то заранее определённого правила. Вопрос именно в случайной перестановке членов массива. |
Re: Перемешать массив чисел | |
---|---|
Extortioner Сообщений: 854 Откуда: Новосибирск Дата регистрации: 06.10.2005 |
Katana, у вас к определено правило - согласно которому для одинаковых начальных условий мы получаем одинаковые выходные данные.
Видимо я на самом деле не совсем корректно поставил условие задачи. То есть выходной набор должен получаться спонтанно. Ну и, желательно, за наиболее короткое время |
Re: Перемешать массив чисел | |
---|---|
Extortioner Сообщений: 854 Откуда: Новосибирск Дата регистрации: 06.10.2005 |
Ну если хотите пример то пожалуйста
1 ый случай массив: 1 2 3 4 5 6 перемешанный массив 6 2 3 4 1 5 Запускаем процедуру ещё раз массив: 1 2 3 4 5 6 перемешанный массив 1 3 2 4 6 5 То есть заранее невозможно предугадать каким будет выходной набор. |
Re: Перемешать массив чисел | |
---|---|
Igor Korolyov Автор Сообщений: 34580 Дата регистрации: 28.05.2002 |
Да ради бога, берёшь и "сдвигаешь" массив циклически на некотрое случайное число элементов. Т.е. было
1 2 3 4 5 6, а стало например 3 4 5 6 1 2 и другой раз 5 6 1 2 3 4 - формально все услвоия соблюдены, хотя от "случайности" тут практически ничего и нету. Кстати, в истинно "случайной" перестановке НЕЛЬЗЯ запрещать некоторому элементу не покидать своего места Иначе это уже не "случайная" перестановка а вполне себе жёстко детерменированная. Т.е. по сути ДАЖЕ вариант где всего 2 элемента поменяют свои места является "случайной" перестановкой (хотя и крайне маловероятной). Другой интересный вопрос - с чего ты взял что возвращаемое RAND значение (наверняка оно лежит в основе "случайной мешалки") является "случайной" величиной? Это абсолютно точно детерменированное значение, и, например, после 0.5713463067 всегда будет следовать 0.6693051432 и НИКОГДА не "выпадет" какое-то другое значение Так что возможно проще всего не "мешать", а тупо генерить каждый раз новый набор, начинающийся с большой долей вероятности с "другой точки" в фоксовой последовательности (её размер, т.е. "период повторения достаточно" большой - порядка 2^32 чисел, но для такой значительной выборки как полмиллиона это уже будет заметно - в самой последовательности получится взять не более чем 9000 разных вариантов перетасовки - остальное будет по сути "склейками" из 2-х "соседних" перестановок) ------------------ WBR, Igor |
Re: Перемешать массив чисел | |
---|---|
Extortioner Сообщений: 854 Откуда: Новосибирск Дата регистрации: 06.10.2005 |
Ну дак, а я и не говорил, что каждый член массива обязательно должен поменять своё местоположение - вот мои слова "каждый элемент массива должен поменять своё местоположение. Ну или хотя бы сделать попытку к изменению" - то есть теоретически может выпасть случай, когда элемент останется на своём месте, но вероятность этого должна быть крайне мала.
По поводу Rand - не знал, что это псевдогенератор, но тем не менее даже с ним выходные наборы не повторяются. Кстати, задача не такая уж и теоретическая, когда я в вузе учился преподаватель при помощи такого алгоритма моделировал какие-то вещи из микромира - то-ли движения молекул то-ли что... Правда там в массиве могли содержаться одинаковые элементы, но разницы в способе решения никакой. |
Re: Перемешать массив чисел | |
---|---|
Goodwin Сообщений: 3539 Откуда: Омск Дата регистрации: 03.05.2006 |
Я так понял эту сумбурную формулировку задачи:
1) должна быть перезапись всех элементов массива 2) функция rand() должна использоваться не менее 500000 раз Т.е. решение должно быть производным от
------------------ Что мы знаем о лисе? Ничего. И то не все. (С)Б. Заходер |
Re: Перемешать массив чисел | |
---|---|
Extortioner Сообщений: 854 Откуда: Новосибирск Дата регистрации: 06.10.2005 |
Наверное я на самом деле не умею задачи ставить
Приведу свой пример решения:
Суть алгоритма - устанавливаю указатель на последний элемент. Выбираю какой-то элемент из всего массива, меняю их местами, при этом сдвигаю указатель на одну позицию влево. На следующей итерации происходит выбор из n-1 членов массива. Таким образом мы получаем ситуацию, когда каждый элемент массива хотя бы попытался изменить своё местоположение. |
Re: Перемешать массив чисел | |
---|---|
Igor Korolyov Автор Сообщений: 34580 Дата регистрации: 28.05.2002 |
Не могу оценить насколько качественно этот алгоритм перемешивает таблицу, я бы поступил проще - в 2-мерном массиве, а лучше в курсоре, во вспомогательное поле/2 колонку поместил случайное число и потом просто отсортировал по этому полю/колонке. При том для курсора можно обойтись вообще без "поля с номером", используя RECNO() - ну для твоей задачи с "номерами от 1 до N" это подходит.
Мне кажется это даёт лучшее "перемешивание", хотя, конечно, и один и другой способ может иметь недостатки, связанные с аномалиями распределения этих самых псевдо-случайных чисел... Просто у тебя для "последних" элементов гарантируется минимальное перемешивание (для самого последнего - по сути лишь 1 "смена"), тогда как для первых таких перетасовок очень много получается (чем короче становится "оставшаяся" часть массива, тем чаще для перестановки выбираются первые элементы) и я не уверен что это хорошо. В этой теме были ссылки на "теоретические основы" (в начале). ------------------ WBR, Igor |
Re: Перемешать массив чисел | |
---|---|
Extortioner Сообщений: 854 Откуда: Новосибирск Дата регистрации: 06.10.2005 |
Пример работы моего алгоритма:
1 2 3 4 5 в пределах [1 .. 5] выпадает 1, мы меняем 1 и 5 5 2 3 4 1 в пределах [1 .. 4] выпадает 2, мы меняем 2 и 4 5 4 3 2 1 в пределах [1 .. 3] выпадает 1, мы меняем 1 и 3 3 4 5 2 1 в пределах [1 .. 2] выпадает 2, мы меняем 2 и 2 3 4 5 2 1 - Ничего не происходит в пределах [1 .. 1] выпадает 1, мы меняем 1 и 1 3 4 5 2 1 - Ничего не происходит За ссылку спасибо, почитаю |
Re: Перемешать массив чисел | |
---|---|
pasha_usue Сообщений: 3649 Откуда: Е-бург Дата регистрации: 06.10.2006 |
Вариант:
PS. Чорд. Поторопился. Не успел до Игоря дочитать. ;) Исправлено 1 раз(а). Последнее : pasha_usue, 24.04.11 13:15 |
Re: Перемешать массив чисел | |
---|---|
Igor Korolyov Автор Сообщений: 34580 Дата регистрации: 28.05.2002 |
"Неравномерность" можно устранить используя RAND()*2^32, а чтобы этот диапазон (от 0 до чуть меньше чем 2^32) помещался в Integer поле дописать -2^31+1
------------------ WBR, Igor |
© 2000-2024 Fox Club  |