Алгоритм Нарайаны. Реализуем на Fortran

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

Лексикографический порядок для перестановок

Перед тем, как перейти к описанию самого алгоритма, стоит определить отношение лексикографического порядка для перестановок. В применении к перестановкам одинаковой длины, лексикографический порядок можно определить так: перестановка A предшествует перестановке B (A < B), если первые n элементов из этих перестановок совпадают, а n+1 элемент B больше n+1 элемента А. Рассмотрим на примере.

Первые n—элементов (в примере первые три) этих перестановок совпадают. Но на n+1 индексе в перестановке B стоит значение больше, чем значение на таком же индексе в перестановке A. В таком случае говорят, что перестановка A предшествует перестановке B. После того, как закончили с формальным определением, можно приступать к описанию самого алгоритма.

Описание алгоритма

Алгоритм для генерации всех перестановок в лексикографическом порядке был предложен индийским математиком Пандитом Нарайаной в XIV веке (так что более классический алгоритм еще нужно поискать). Этот крупный индийский математик внес весомый вклад в арифметику, алгебру и комбинаторику. И именно, одна из его работ по комбинаторике и подарила нам алгоритм, носящий его имя.

Алгоритм Нарайаны

1. Создать последовательность длиной n. Заполнить целыми числами (по возрастанию) в диапазоне от 1 до n. Перейти к пункту 2.
2. Использовать последовательность как очередную перестановку. Перейти к пункту 3.
3. Начиная с конца последовательности выполнить поиск элемента, правый сосед которого больше его (назовем его a). Если такой элемент найден перейти к пункту 4. В противном случае закончить алгоритм.
4. Начиная с конца последовательности, выполнить поиск элемента, значение которого больше значения элемента, найденного в пункте 3 (назовем его b). Выполнить их обмен. Провести реверс части последовательности, начиная от элемента следующего за элементом найденным в пункте 3 и до конца. Перейти к пункту 2.

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

Как вы видите, этот алгоритм действительно прост для запоминания (да и реализация также не намного сложнее), но какова же его асимптотическая сложность? В наилучшем случае для генерации перестановки нужно выполнить одно сравнение и один обмен (предпоследний элемент меньше последнего). В наихудшем же случае (окончание алгоритма), получится приблизительно n сравнений. Так что можно сказать, что асимптотическая сложность получения одной перестановки O(n), но так как самих перестановок n!, то сложность получения всех перестановок факториальна O(n!).

Давайте закрепим текстовое объяснение с помощью графического примера. Рассмотрим генерацию всех перестановок длинной 3 (на примере нескольких итераций).

Сначала просто создаем последовательность из трех элементов. Заполним от единицы по возрастанию и используем в качестве очередной перестановки (используемые перестановки обозначены оранжевым кругом). После чего, с конца последовательности, ищем элемент (элемент a), сосед которого справа больше, чем он. Это элемент со значением 2 (соседний элемент справа равен 3 и он больше). Следом с конца последовательности ищем элемент, значение которого больше найденного ранее (элемент b), после чего производим их обмен и реверс последовательности от элемента a и до конца. Используем последовательность как очередную перестановку.

Рассмотрим еще одну итерацию. Начиная с конца последовательности ищем элемент, сосед которого справа больше него (элемент a). Начиная с конца последовательности, ищем элемент, больше найденного (элемент b). Выполняем их обмен, проводим реверс элементов последовательности, начиная от элемента a и до конца. Используем последовательность в качестве очередной перестановки и т. д.

Что же будет условием окончания алгоритма? Это будет случай, когда во всей последовательности не найдется такого элемента, сосед которого справа больше. Этот случай приведен ниже.

После объяснения алгоритма приступим к его реализации на языке Fortran.

Реализация на Fortran

program narayana_algorithm
implicit none
integer::n

write(*,*) 'Input n'
read(*,*) n
call print_all_permutation(n)

contains

subroutine print_all_permutation(n)
   implicit none
   integer,intent(in)::n
   integer::sequence(n)
   integer::i
   logical::has_next_permutation = .true.
   sequence = [(i,i=1,n)]
   do
      write(*,*) sequence
      call next_permutation(sequence,has_next_permutation)
      if(.not. has_next_permutation) then
         exit
      end if
   end do
end subroutine print_all_permutation

subroutine next_permutation(sequence,has_permutation)
   implicit none
   integer, intent(inout)::sequence(:)
   logical, intent(inout)::has_permutation
   integer::i,j,n
   has_permutation = .false.
   n = size(sequence, dim = 1)
   do i = n-1, 1, -1
      if(sequence(i) < sequence(i+1)) then
         has_permutation = .true.
         exit
      end if
   end do
   if(.not. has_permutation) then
      return
   end if
   do j = n, 1, -1
      if(sequence(j)>sequence(i)) then
         call swap_element(sequence,i,j)
         call reverse(sequence,i+1)
         exit
      end if
   end do
end subroutine next_permutation

subroutine reverse(sequence, k)
   implicit none
   integer, intent(inout)::sequence(:)
   integer, intent(in)::k
   integer::i,j,n
   n = size(sequence, dim = 1)
   j = n 
   do i = k, (k+n)/2
      call swap_element(sequence,i,j)
      j = j - 1
   end do
end subroutine reverse

subroutine swap_element(sequence, i, j)
   implicit none
   integer, intent(inout)::sequence(:)
   integer, intent(in)::i,j
   integer:: temp
   temp = sequence(i)
   sequence(i) = sequence(j)
   sequence(j) = temp
end subroutine swap_element  
end program narayana_algorithm

Для компиляции этого примера сохраните исходный код в файл с расширением f90 (например narayana.f90) и используйте современную версию gfortran или аналогичный компилятор. Помня пожелания читеталей с прошлой статьи, в этот раз размер перестановки вводится с клавиатуры при старте программы.

Также в комментариях к прошлой статье подняли интересный вопрос, а как этот алгоритм отнесется к перестановкам упорядоченного мультимножества? Например, такого [1,2,2,3]. Для проверки слегка изменим основной код программы (все процедуры оставим без изменения)

program narayana_algorithm
implicit none
integer::arr(4)
logical::has_next = .true.
arr = [1,2,2,3]
do
   write(*,*) arr
   call next_permutation(arr,has_next)
   if(.not. has_next) then
      exit
   end if
end do

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

Послесловие

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

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