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

From

Sergej Tarasov (2:5020/175.2)

To

Evgenij Masherov

Date

2003-01-03T03:29:11Z

Area

RU.ALGORITHMS

From: "Sergej Tarasov" <tarasov@pmi.lv>

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)