Алгоритм перемешивания массива

Очередной раз встретилась простая, но интересная задача – в заданном массиве перемешать имеющиеся значения.

Иногда эта задача еще формулируется как заполнение массива неповторяющимися значениями в случайном порядке. Но писать алгоритм, который будет генерировать случайное число, затем проверять, не повторится ли это значение с уже заполненными элементами, нерационально. Гораздо правильней будет просто перемешать заданный массив. Тем более, что это позволит не усложнять процесс подбора допустимых значений, соблюдая уникальность каждого значения или учитывая вхождение каждого значения заданное количество раз.

В итоге, задача сводится только к перемешиванию имеющейся последовательности не зависимо от ее исходного состава и упорядоченности.

Самое простое решение было бы в цикле выполнить N операций замены двух элементов, индексы которых выбираются случайно. Величина N определяет качество такого перемешивания – чем больше замен, тем качественнее результат. Недостаток этого метода заключается в том, что некоторые элементы массива (особенно если он большой), могут остаться на своих исходных местах. Так же недостаток будет возможность многократного перемещения одного и того же элемента массива. В итоге, нерациональное увеличение количества замен, все же не ведет к 100% качественной перетасовке всех элементов.

Более качественный и в плане перемещения всех элементов, и в количестве операций перемешивания следующий алгоритм:

• выбираем случайный элемент массива;
• меняем его местами с последним элементом;
• снова выбираем случайный элемент массива, не затрагивая последний;
• меняем с предпоследним;

Рисунок: Алгоритм перемешивания массива

Таким образом, выбираем из сужающегося списка случайный элемент и ставим последним в этом списке. Для перемещения всех элементов потребуется на одно перемещение меньше, чем количество элементов в массиве.

const
   N = 9; // размер массива
var
   mas : array[1..N] of Integer;
   i, r, h : Integer;
begin
   Randomize;
   for i := N downto 2 do begin
      r := Random(i) + 1; // выбор случайного элемента

      if r <> i then begin
      // замена элементов
      h := mas[i];
      mas[i] := mas[r];
      mas[r] := h;
    end;
  end;
end;

В данном решении существует вероятность выпадения в качестве случайного элемента того, на который производится замена. Чтобы избежать бессмысленного перемещения одного элемента имеется проверка, которая исключит лишнюю замену. Однако, в таком случае, есть вероятность, что некоторые элементы массива могут остаться на своем месте.

Чтобы исключить этот недостаток, можно делать выборку случайного значения, не затрагивая крайний заменяемый элемент. Так как заранее известно, что заменяемый элемент выбран быть не может, дополнительное условие здесь не нужно.

const
   N = 9; // размер массива
var
   mas : array[1..N] of Integer;
   i, r, h : Integer;
begin
   Randomize;
   for i := N downto 2 do begin
       r := Random(i-1) + 1; // выбор случайного элемента

       // замена элементов
       h := mas[i];
       mas[i] := mas[r];
       mas[r] := h;
    end;
end;

Применение такого алгоритма гарантирует, что ни один элемент не останется на прежнем месте.