Добрый день, давайте попробуем решить такую задачку:
Дан массив чисел, от 1 до n пусть n будет достаточно большим.
Необходимо перемешать этот массив случайным образом.
Мне удалось на своём не самом быстром компьютере добиться значения 1,656 сек для
n = 500 000
Естественно вывод не учитываем - проверяем правильность работы процедуры на малых n.

Ну и небольшое дополнение для любителей простых решений (ведь можно сказать, что если мы поменяем просто два элемента массива местами то массив перемешан ) - каждый элемент массива должен поменять своё местоположение. Ну или хотя бы сделать попытку к изменению



Исправлено 3 раз(а). Последнее : Extortioner, 19.04.11 14:15

А каков критерий случайности?
Если я массив в обратном порядке или сначала чёт/потом нечёт выведу проканает?

Пробный шар (т.к. не совсем понял условие)

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

Goodwin
А каков критерий случайности?
Если я массив в обратном порядке или сначала чёт/потом нечёт выведу проканает?

Не, ну каждый раз мы должны получать разные наборы чисел на выходе - то есть не должно быть какого-то заранее определённого правила. Вопрос именно в случайной перестановке членов массива.

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

Ну если хотите пример то пожалуйста
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

То есть заранее невозможно предугадать каким будет выходной набор.

Да ради бога, берёшь и "сдвигаешь" массив циклически на некотрое случайное число элементов. Т.е. было
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-х "соседних" перестановок)

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

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

Я так понял эту сумбурную формулировку задачи:
1) должна быть перезапись всех элементов массива
2) функция rand() должна использоваться не менее 500000 раз

Т.е. решение должно быть производным от

Наверное я на самом деле не умею задачи ставить

Приведу свой пример решения:

Суть алгоритма - устанавливаю указатель на последний элемент. Выбираю какой-то элемент из всего массива, меняю их местами, при этом сдвигаю указатель на одну позицию влево. На следующей итерации происходит выбор из n-1 членов массива. Таким образом мы получаем ситуацию, когда каждый элемент массива хотя бы попытался изменить своё местоположение.

Не могу оценить насколько качественно этот алгоритм перемешивает таблицу, я бы поступил проще - в 2-мерном массиве, а лучше в курсоре, во вспомогательное поле/2 колонку поместил случайное число и потом просто отсортировал по этому полю/колонке. При том для курсора можно обойтись вообще без "поля с номером", используя RECNO() - ну для твоей задачи с "номерами от 1 до N" это подходит.
Мне кажется это даёт лучшее "перемешивание", хотя, конечно, и один и другой способ может иметь недостатки, связанные с аномалиями распределения этих самых псевдо-случайных чисел... Просто у тебя для "последних" элементов гарантируется минимальное перемешивание (для самого последнего - по сути лишь 1 "смена"), тогда как для первых таких перетасовок очень много получается (чем короче становится "оставшаяся" часть массива, тем чаще для перестановки выбираются первые элементы) и я не уверен что это хорошо.
В этой теме были ссылки на "теоретические основы" (в начале).

Пример работы моего алгоритма:
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 - Ничего не происходит

За ссылку спасибо, почитаю

Вариант:
Данный способ дает небольшую неравномерность распределения. Дело в том, что числа, получившие одинаковый индекс фокс отсортирует по порядку записей в таблице (то-есть в порядке возрастания). Неравномерность можно устранить, если вместо целых чисел использовать DOUBLE. Но индекс тогда работает медленнее.

PS. Чорд. Поторопился. Не успел до Игоря дочитать. ;)



Исправлено 1 раз(а). Последнее : pasha_usue, 24.04.11 13:15

"Неравномерность" можно устранить используя RAND()*2^32, а чтобы этот диапазон (от 0 до чуть меньше чем 2^32) помещался в Integer поле дописать -2^31+1