Re: масив чисел

From

Evgenij Masherov (2:5020/175.2)

To

Sergej Tarasov

Date

2003-01-03T03:59:16Z

Area

RU.ALGORITHMS

From: "Evgenij Masherov" <EMasherow@nsi.ru>

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)