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

From

Evgenij Masherov (2:5020/175.2)

To

Oleg Khovayko

Date

2003-01-03T02:58:20Z

Area

RU.ALGORITHMS

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

Fri Jan 03 2003 02:39, Oleg Khovayko wrote to Evgenij Masherov:

 
 OK> Я же еще 29 декабря в своем письме кидал
 OK> сюда алгоритм перемешивания, не требующий
 OK> ни доп. памяти, ни сортировки, и делающий
 OK> перемешивание за 1 проход - за N().

 OK> Или вы не получали сообщения, или читали не до конца?
 OK> Непонятно. Повторяю еще раз алгоритм перемешивания:

 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> Во, дешево и сердито...

Дешево. Сердито. И неверно. В том смысле, что равновероятность всех
перестановок не обеспечивается. Хотя если нужно только сделать некоторое
возмущение расстановки - может и сойти.
Похоже, что вообще гарантировать равновероятность менее чем за NlogN операций
не выйдет...

Евгений Машеров АКА СанитарЖеня

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)