|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 29 Jan 2003 18:45:26
To : Evgenij Masherov
Subject : масив чисел
--------------------------------------------------------------------------------
Replying to a message of Evgenij Masherov to Oleg Khovayko:
OK>> Я же еще 29 декабря в своем письме кидал
OK>> сюда алгоритм перемешивания, не требующий
OK>> ни доп. памяти, ни сортировки, и делающий
OK>> перемешивание за 1 проход - за N().
OK>> Или вы не получали сообщения, или читали не до конца?
OK>> Hепонятно. Повторяю еще раз алгоритм перемешивания:
OK>> int mas[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
OK>> for(int i = 9; i > 0; i--) {
OK>> int j = random() % i;
OK>> int tmp = mas[j];
OK>> mas[j] = mas[i];
OK>> mas[i] = tmp;
OK>> }
OK>> Во, дешево и сердито...
EM> Дешево. Сердито. И неверно. В том смысле, что равновероятность всех
EM> перестановок не обеспечивается.
Как я понял, вкралась очепяточка - должно быть
int j = random() % (i+1);
EM> Хотя если нужно только сделать
EM> некоторое возмущение расстановки - может и сойти. Похоже, что вообще
EM> гарантировать равновероятность менее чем за NlogN операций не
EM> выйдет...
Такое перемешивание - классика, описанная еще у Кнута.
N операций достаточно!
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.8
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
