Генерируем перестановки с помощью алгоритма циклических сдвигов. Реализация на Fortran

Добрый день, я Александр Цымбалюк, работаю научным сотрудником в Киевском национальном университете имени Тараса Шевченко на факультете радиофизики, электроники и компьютерных систем (кафедра физической электроники). Предыдущая моя статья была о вычислительной плазмохимии (я надеюсь, будут и еще), но эта статья будет посвящена еще одной моей страсти, а именно изучению алгоритмов и их реализации на Fortran. Предлагаю вашему вниманию интересный комбинаторный алгоритм для генерации перестановок множества.

Генерация всех перестановок множества

Заранее стоит условиться, что в качестве модельного множества я буду использовать множество целых чисел из определенного диапазона с шагом в единицу, например такое {1,2,3...}. С чем связан подобный выбор? В большинстве языков программирования есть такие структуры данных как массивы и списки. Эти структуры данных характеризуются доступом к значениям с помощью индексов, а индексы — это целые числа из определенного диапазона с шагом в единицу. И тут и пригодится тот факт, что в качестве модельного множества использовалось множество целых чисел. Эти числа вы сможете использовать как индексы, и как следствие очень легко получите перестановки для множества значений любого типа (строки, кошки и товары). Достаточно будет просто поместить их в массив или список и использовать числа из модельного множества в качестве индексов.

Ну а теперь вернемся к перестановкам. Перестановка — набор чисел {1, 2, ... , n} без повторения, выступающий как биекция на множестве { 1, 2, ... , n }, которая числу i ставит в соответствие i-й элемент из набора. Число n при этом называется длиной перестановки. Проиллюстрируем это на примере:

Пускай у нас есть множество кошек (изображено слева). Пронумеруем их начиная с 1-й. Это базовое множество. Его перестановки изображены справа. Положение числа определяет положения элемента в множестве, а значение числа — номер элемента из базового. Так, перестановка вида [1,3,2] предполагает, что на первом месте стоит первый элемент из базового множества, на втором месте — третий элемент из базового, на третьем месте должен стоять второй элемент из базового множества. Можно предложить только 6 вариантов перестановок этих цифр (биективных отображений) и как следствие перестановок этого множества. Полное количество перестановок для множества размера n вычисляется как:

В примере у нас три элемента (три кота), и количество перестановок в этом случае:

Бегло вспомнив, что такое перестановки, перейдем к алгоритму их генерации. Довольно интересным и простым для запоминания является алгоритм циклических сдвигов.

Алгоритм циклических сдвигов

1. Создать последовательность (массив) размером n. Заполнить ее значениями равными индексам элементов. Создать вспомогательную переменную (в примере k). Установить ее значение, равное индексу последнего элемента. Перейти к пункту 2.
2. Использовать последовательность как очередную перестановку. Установить значение k, равное индексу последнего элемента. Перейти к пункту 3.
3. Выполнить циклический сдвиг влево элементов последовательности от первого до k-го. Если k-й элемент последовательности не равен k, то перейти к пункту 2. В противном случае перейти к пункту 4.
4. Указать новое значение k = k — 1. Если k равен индексу первого элемента последовательности, то закончить алгоритм. В противном случае перейти к пункту 3.

И тут сразу стоит определиться с тем, что такое циклический сдвиг влево. Под циклическим сдвигом влево подразумевается смещение всех значений последовательности на одну позицию влево. При этом первый элемент последовательности становится последним элементом. Если выполнить сдвиг влево определенное количество раз (размер последовательности), то получим опять начальную последовательность. Поэтому сдвиг и называют циклическим.

На рисунке продемонстрирована последовательность циклических сдвигов для последовательности размером 3.

Закончив с определением циклических сдвигов, перейдем к алгоритму. Попробуем проиллюстрировать графически данный алгоритм для перестановок размером 3. Те перестановки, которые будут использованы (пункт 2 алгоритма), отметим оранжевым кругом. Индексация в последовательности начинается с единицы.

Начинаем с базовой последовательности (ее элементы равны значению индексов), устанавливаем k = 3 и начинаем выполнять сдвиги с первого по k-й элемент до тех пор, пока на индексе k опять не появится значение, равное k. Потом уменьшаем k на единицу и выполняем сдвиг с первого по k-й элемент.

Теперь на k стоит значение, не равное k, следовательно можно опять перейти к пункту 2.

Тут опять используем полученную перестановку, устанавливаем k равным последнему индексу и выполняем сдвиги до тех пор, пока на k-м индексе не появится элемент, равный k. Уменьшаем k на единицу и выполняем сдвиг с первого по k-й элемент.

Но опять получаем, что на k-м индексе стоит элемент, равный k. Опять уменьшаем k на единицу.

Но теперь значение k равно первому индексу и следовательно алгоритм нужно заканчивать.

После рассмотрения описания алгоритма, осталось его реализовать на любом удобном для вас языке программирования. Одним из используемых мной в работе языков программирования является Fortran (да, этот старичок еще как в строю), так что приведу реализацию именно на нем.

program cyclic_shift_permutation
implicit none

integer::n

n = 3

call creating_permutations(n) !Получить все перестановки длиной n 

contains

subroutine left_shift(sequince,k)
   implicit none
   integer,intent(inout)::sequince(1:)
   integer,intent(in)::k
   integer::temp, i
   
   temp = sequince(1)
   do i = 1,k-1
      sequince(i) = sequince(i + 1)
   end do
   sequince(k) = temp
end subroutine left_shift

subroutine creating_permutations(n)
   implicit none
   integer,intent(in)::n
   integer::sequince(1:n)
   integer::i, k
   
   sequince = [(i, i = 1,n)] !Заполняем массив его индексами
   k = n
   write(*,*) sequince
   do
      call left_shift(sequince,k) !Сдвиг влево
      if(sequince(k)/=k) then !Если на k-м индексе элемент не равен k
         write(*,*) sequince
         k = n
      else  !Уменьшаем k на единицу
         k = k - 1
      end if
      
      if (k==1) then !Если k равен первому индексу заканчиваем
         exit
      end if
   end do
end subroutine creating_permutations

end program cyclic_shift_permutation

Осталось только скомпилировать пример. Это можно сделать, например, с помощью свободного компилятора gfortran и можно запускать. Правда, не стоит ставить слишком большим длину перестановки. Так, для n=10 вы получите 10! = 3628800 перестановок, и просто вывод их на экран может занять значительное время. Если есть желание, то можно использовать в качестве своеобразной заставки в стиле матрицы, на экране будут долго выводиться наборы чисел.

Надеюсь вам также понравился этот элегантный алгоритм и вы добавите его к своей коллекции. Если вас заинтересует, есть видеолекция об этом алгоритме на моем канале на YouTube — (там еще много разных алгоритмов :) А на этой ноте благодарю вас за внимание и до следующих встреч.

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті