|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 03 Jan 2003 18:03:07
To : Evgenij Masherov
Subject : Re: масив чисел
--------------------------------------------------------------------------------
Evgenij Masherov wrote:
>
> EM>> Дешево. Сердито. И неверно. В том смысле, что равновероятность всех
> EM>> перестановок не обеспечивается.
>
> В приведенном алгоритме третий элемент принципиально не может оказаться на
> третьем месте. Т.е. две перстановки из шести (и одна - со вторым) выпадают...
>
Мда, есть такое. Hо клиенту же нужно "гарантированое перемешивание", поэтому
приведенный ранее алгоритм как раз его и обеспечивает, искусственно исключая
вырожденые случаи. Кроме того, он чуть-чуть проще "математически верного".
Поэтому именно его я и рекомендовал для практической реализации.
Если же интересует именно "математически верный" алгоритм, то вот он:
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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
