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