Форум «Всё о Паскале» _ FAQ _ Как правильно перемешивать массивы
Автор: TarasBer 2.08.2011 10:44
Есть задача - надо получить набор случайно перемешанных чисел от 1 до n. Как её решить? Наивный алгоритм: добавлять в новый массив случайное число от 1 до n, каждый раз проверяя, не входит ли оно уже в массив:
for i := 1 to n do begin repeat candidat := random(n) + 1; // от 1 до n can := true; for j := 1 to i-1 do if ARR[j] = candidat then begin can := false; break; end; until can; ARR[i] := candidat; end;
Этот алгоритм плох тем, что для подбора последнего, например, элемента придётся прогонять цикл в среднем n раз - ведь у нас все номера уже заняты, кроме одного, поэтому вероятность того, что мы попадём на этот один элемент, равна 1/n. Для предпоследнего придётся делать в среднем n/2 попыток, так что можно посчитать алгоритмическую сложность такого метода, она будет n+n/2+n/3+...+n/n ~ n*log(n) К тому же есть цикл, у которого условие выхода определяется исходя из значения случайной величины, а значит, есть возможность, что из-за несовершенства ГСЧ цикл никогда не завершится.
Есть старый алгоритм, который намного лучше. Составляем упорядоченный массив, потом последний элемент меняем с любым, предпоследний меняем с любым, кроме последнего, предпредпоследний - с любым, кроме последнего и предпоследнего, и так далее.
for i := 1 to n do ARR[i] := i; for i := n downto 2 do begin // первый трогать нет смысла j := random(i)+1; // от 1 до i, значение i тоже допустимо swap(i,j); // меняем местами элементы, стоящие на итом и на житом местах end;
Алгоритмическая сложность - O(n).
Данный метод можно применять и для генерации поля в сапёре - пронумеровать ячейки числами от 1 до кол-ва ячеек (n), перемешать номера, поставить бомбы на те клетки, в которых номера не больше, чем кол-во бомб (m).
Можно чуть оптимизировать: без перемешивания поставить бомбы только на последние m клеткок, потом применить алгоритм перемешивания, но прогонять только от n до n-m+1. Можно посчитать вероятность наличия бомбы в любой клетке, она окажется ровно m/n.