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

From

Oleg I. Khovayko ()

To

Evgenij Masherov

Date

2003-01-03T17:03:07Z

Area

RU.ALGORITHMS

From: "Oleg I. Khovayko" <olegh@ncbi.nlm.nih.gov>

Evgenij Masherov wrote:

> 
>  EM>> Дешево. Сердито. И неверно. В том смысле, что равновероятность всех
>  EM>> перестановок не обеспечивается. 
> 
> В приведенном алгоритме третий элемент принципиально не может оказаться на
> третьем месте. Т.е. две перстановки из шести (и одна - со вторым) выпадают...
> 

Мда, есть такое. Но клиенту же нужно "гарантированое перемешивание", поэтому
приведенный ранее алгоритм как раз его и обеспечивает, искусственно исключая
вырожденые случаи. Кроме того, он чуть-чуть проще "математически верного".
Поэтому именно его я и рекомендовал для практической реализации.

Если же интересует именно "математически верный" алгоритм, то вот он:

int mas[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

for(int i = 9; i > 0; i--) {
   int j = random() % (i + 1);
   if(i != j) {
     int tmp = mas[j];
     mas[j] = mas[i];
     mas[i] = tmp;
   }
}

Смысл следуюший:
Пусть у нас есть колода карт (игральных). Ее надо перемешать.
Простейший вариант перемешивания такой: 

Пока колода не пуста:
	Извлекаем из колоды 
	случайную карту, и ложим ее в отдельную стопку.

Приведенный выше алгоритм - как раз программная 
реализация этой идеи, где входная и выходная стопки совмещены.

-- 
#include <best/regards.hpp>
Oleg I. KHOVAYKO  
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
 * Origin: National Center for Biotechnology Information (2:5020/400)