Существуют ли алгоритмы перемешивания массива способные удивить? В статье будут рассмотрены наиболее популярны алгоритмы перемешивания.
Есть целочисленный массив размером 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;
Суть алгоритма в том, чтобы не делать лишних операций и перемешать абсолютно все элементы.
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. Постоянно генерировать случайное число из заданного диапазона и сравнивать с уже полученными ранее, если оно уникально — вычисляем следующее.
// может вычислять очень долго, делает много лишних операций, перемешивает все — худший из всех приведенных, в теории может зависнуть;
Дорогие читатели, давайте узнаем — есть ли алгоритмы лучше и надежнее? Интереснее? Напишите в комментариях.
Тут язык не имеет значения, хотя если есть интересные реализации в специфических языках — напишите, пожалуйста, в комментариях.
