|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergej Tarasov 2:5020/175.2 03 Jan 2003 04:29:11
To : Evgenij Masherov
Subject : Re: масив чисел
--------------------------------------------------------------------------------
Fri Jan 03 2003 02:58, Evgenij Masherov wrote to Oleg Khovayko:
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> перестановок не обеспечивается. Хотя если нужно только сделать некоторое
EM> возмущение расстановки - может и сойти.
EM> Похоже, что вообще гарантировать равновероятность менее чем за NlogN
EM> операций не выйдет...
Если я не ошибаюсь, то тут как раз равновероятность перестановок
обеспечивается. К примеру, возьмем массив из 3 элементов. После
перестановок любой элемент может оказаться на любом месте с вероятностью 1/3.
При первой перестановке берем третий элемент и ставим на это место
любой из трех - итого, на последнем месте окажется любой эелемент
с вероятностью 1/3. Вероятность того, что он не окажется на последнем
месте - 2/3. Затем берем второй элемент и на его место ставим любой
из двух оставшихся - то есть вероятность того, что какой-либо элемент
окажется на второй позиции - 2/3*1/2=1/3. Точно также для четырех
элементов получается, что вероятность появления эелемнта на любой
позиции равна 1/4. И для 5-ти элементов все получается. Дальше
не проверял.
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
