Как правильно перемешивать массивы, получение случайного распределения в массиве Опции

[TarasBer]

Есть задача - надо получить набор случайно перемешанных чисел от 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.