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

в 21:42, , рубрики: Песочница, метки:

Существуют ли алгоритмы перемешивания массива способные удивить? В статье будут рассмотрены наиболее популярны алгоритмы перемешивания.

Есть целочисленный массив размером 100 и значениями от 1 до 100.

Надо его перемешать.
Например: 1 2 3 4 5 ---> 4 2 1 5 3

Самый простой, надежный и качественный алгоритм в теории это:

const
  N = 100;
var
  i,j,c,ri:integer;
  a,b:array[1..N]of Byte;
  //a - массив, в котором будет записан перемешанный массив;
  //b - буферный массив;

begin
Randomize;
for i:=1 to N do b[i]:=i; //Заполняем массив значением соответствующему его порядковому номеру;
  c:=N; 

  for i:=1 to N do begin // проходим от a[1] до a[100]; 
    ri:=random(C)+1; //генерируем случайное число;
    a[i]:=b[ri]; //присваиваем случайный элемент;
    for j:=ri to c-1 do b[j]:=b[j+1]; //удаляем из буферного массива присвоенный массиву <i>a</i> элемент;
    c:=c-1; //сокращаем количество не назначенных элементов;
  end;

  for i:=1 to N do write(a[i],' '); //выводим результат на экран;

end;

Суть алгоритма в том, чтобы не делать лишних операций и перемешать абсолютно все элементы.

Принцип работы алгоритма

1. Берется пустой массив — a. Берется массив для буфера — b. Массив b заполняется значениями от 1 до 100 в соответствии с индексом элемента.

2. Цикл проходит от 1 до 100 присваивая элементу массива a[i] значение случайного элемента из массива b.

3. Затем из массива b удаляется присвоенный массиву a элемент.

Например: значение массива b было = 1 2 3 4 5. Присвоили 3-й элемент массиву a и удаляем это значение из массива b. В итоге массив b стал = 1 2 4 5.

Алгоритмы:

1. Алгоритм, который продемонстрирован выше. Этот алгоритм проходит от 1 до 100, заполняет основной массив случайным элементом из буферного массива, из которого удаляются уже использованные элементы.
// проходит один раз, перемешивает гарантированно все, использует второй массив;

Другие алгоритмы:
2. Алгоритм, который меняет местами два элемента и это повторяется нужное количество раз.
// повторяется много раз, перемешивает не все, простота реализации;

3. Пробегаемся по всем элементам слева от первого до последнего и меняет текущий элемент со случайным элементом из правой части местами. (по сути 1 способ, только подход другой)
//проходит один раз, перемешивает гарантированно все, возможна многократная перезапись одного элемента;

4. Постоянно генерировать случайное число из заданного диапазона и сравнивать с уже полученными ранее, если оно уникально — вычисляем следующее.
// может вычислять очень долго, делает много лишних операций, перемешивает все — худший из всех приведенных, в теории может зависнуть;

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

Поделиться

* - обязательные к заполнению поля