Мы создаем космические сайты

СтатьиСтатьи об алгоритмах программирования

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

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

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

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

Самое простое решение было бы в цикле выполнить 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;

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


Комментарии

07.12.2015 13:52 Fox [гость]
Отличное решение. Просто и удобно.
04.04.2016 16:33 Игорь [гость]
Очень понятный и простой алгоритм. Спасибо.
09.11.2016 15:34 Пётр [гость]
Алгоритм прост и универсален:большое спасибо сайту space-base.ru
10.09.2018 02:14 Borg [гость]
Жаль, что раньше не попалась мне эта статья: опасаюсь, что никто мой коммент читать не будет! Тем не менее рискну.
Сам по себе алгоритм мне тоже понравился, вопросы вызвала концепция: "задача – в заданном массиве перемешать имеющиеся значения", далее несколько раз упоминается слово "случайно". И в конце "алгоритм гарантирует, что ни один элемент не останется на прежнем месте". А зачем, собственно? Случайность результата подразумевает возможность, что один или несколько элементов останутся на своих местах. Далее, в постановке задачи не совсем однозначно задано, что лежит в ячейках массива. Это числа 1-100 или это смесь чисел, слов, картинок? Во втором случае содержимое ячеек может повторяться, но сортировать можно номера ячеек.
Возможно, алгоритм понадобился для составления графика отпусков или схемы ротации сотрудников? Тогда на первом месте критерий "перемены", а случайность выбора очередного элемента обеспечивает социальную справедливость? :-)
Вот именно критерии определения качества перемешивания массива меня и интересуют, даже без элемента случайности.
14.09.2018 22:27 Антон [администратор]
Добрый вечер, Borg.
Случайность перемещения, для перемешивания массива, естественно, допускает то, что какие-то элементы могут остаться на местах. Добавка для гарантии смещения всех элементов, это скорее оговорка для возможного частного случая, если кому-то это будет нужно. Лично мне эта возможность кажется интересной. Хотя не скажу, что применял ее где-то.

Раздел статей "Алгоритмы" содержит описание приемов, которые можно использовать как при обучении, так и в полевых условиях. Все это на усмотрение читателя. Традиционно, для объяснения материала задаются наиболее простые типы данных. В данном случае, подразумеваются целые числа. На это указывает тип массива. Однако, учитывая то, что работа в основном ведется с ключами массива, можно использовать произвольные типы данных. Думаю, даже для социальной задачи формирования очереди отпускников такой подход подойдет.

Комментарии конечно же читаем.
21.09.2018 00:57 Borg [гость]
Спасибо, все понятно. Да, именно такой подход мне нравится: случайность не абсолютная ценность, ее относительная важность меняется от задачи к задаче. С удивлением наткнулся на размышления легендарного Кнута о случайности, там тоже есть несколько скептических пассажей. Ну, это уже отдельная тема.
С уважением,
Имя:
Текст комментария:
* В комментариях запрещено публиковать рекламные объявления. Сообщения, содержащие ссылки на сторонние ресурсы добавляется в скрытом режиме. Они будут открыты, если не нарушают установленных правил, после проверки.
Защита от спам-роботов (* Обязателельно укажите ответ на простой вопрос ниже.)
Сколько букв в слове «барабан»? (цифра)
Индекс цитирования Рейтинг@Mail.ru

2014-2019 space-base.ru