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

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

Добрый день, я Александр Цымбалюк, работаю научным сотрудником в Киевском национальном университете имени Тараса Шевченко на факультете радиофизики, электроники и компьютерных систем (кафедра физической электроники). Предыдущая моя статья была о вычислительной плазмохимии (я надеюсь, будут и еще), но эта статья будет посвящена еще одной моей страсти, а именно изучению алгоритмов и их реализации на 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 — (там еще много разных алгоритмов :) А на этой ноте благодарю вас за внимание и до следующих встреч.

Сподобалась стаття? Натискай «Подобається» внизу. Це допоможе автору виграти подарунок у програмі #ПишуНаDOU

👍ПодобаєтьсяСподобалось46
До обраногоВ обраному3
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Хм,
1) Не основное, но правильно писать «sequence».
2) Может, n брать из командной строки? как это сделать в gfortran? гугл подсказывает getarg(), но мне облом потом разбираться, что лучше — read, ichar или ещё что-то.
3) Почему не тот алгоритм, который выдаёт перестановки в лексикографическом порядке? он не сложнее, но смотреть на результаты проще.
4) Или у вас съедена опция для freeform, или суффикс надо было поставить, но я с ходу 6 пробелов поставлял и тогда оно зашевелилось.
5) .eq., .ne. как-то привычнее :)

А так — неожиданно, конечно :)

День добрый. Спасибо за проявленный интерес, попробую ответить на все вопросы (тут уж конечно как смогу).
1) Каюсь.... Ну, что тут скажешь.
2) Действительно можно считать n с командной строки и в самом простом случае можно использовать обычный read. Например можно сделать так:

write(*,*) ’Input n’
read(*,*) n

3) Ну значит будет отдельная публикация по алгоритму Нарайаны. Действительно гулять, так гулять. Надеюсь редакция ДОУ позитивно отнесется к алгоритмам и Fortran.

4) В gfortran (а это основной компилятор который я использую в работе. Хотя в последнее время присматриваюсь к developer.nvidia.com/hpc-compilers на вид очень перспективно) freeform включен по умолчанию уже много лет. Вот поэтому и подумал, что во всех компиляторах ситуация сходная. А в каком компиляторе этот код не собирается?

5) Ну это дело вкуса, мне математическая нотация ближе (я ведь научный сотрудник :) ).

freeform включен по умолчанию уже много лет.

Чуть не так. Цитата из его info:

> Source files with ’.f’, ’.for’, ’.fpp’, ’.ftn’, ’.F’, ’.FOR’, ’.FPP’, and ’.FTN’ extensions are treated as fixed form. Source files with ’.f90′, ’.f95′, ’.f03′, ’.f08′, ’.F90′, ’.F95′, ’.F03′ and ’.F08′ extensions are treated as free form. The capitalized versions of either form are run through preprocessing. Source files with the lower case ’.fpp’ extension are also run through preprocessing.

Видимо, вы по умолчанию ставите суффикс .f95 (или какой там вариант актуален? вроде для этого кода 95-го достаточно). Я сделал .f по инерции со старым подходом.

и в самом простом случае можно использовать обычный read

Ну да, это вообще классика. И для тестов стиля acmp обычно такое проходит, а не через командную строку. Всяко лучше чем перекомпилировать.

5) Ну это дело вкуса, мне математическая нотация ближе

Аргумент. Но я уже тупо не помню, в какой версии начали допускать этот стиль.

Действительно всегда использовал расширение f90 (вроде сейчас стандарт) вот и не ведал проблем с свободной формой. Теперь учту. Как говориться — «Век живи, век учись».

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

есть набор встроенных функций, их множество и перезагрузок у них ещё больше. но обычно хватает двух: command_argument_count() и get_command_argument(integer, character*). в реальной вычислительной жизни чаще перенаправляется входной поток из файла.

Ну... очень подробно этот вопрос разобран у Дональда Кнута TAoCP 7.2.1.2, краткое ревью примерно такое

Вообще-говоря в общем случае элементы могут повторяться, например для 1223 можно получить перестановки 1223, 1232, 1322, 2123, 2132, 2213, 2231, 2312, 2321, 3122, 3212, 3221, и тут алгоритм пасует.

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

Интересным применением перебора перестанновок является решение буквометриков SEND + MORE = MONEY. И тут перебор хочется делать не случайным образом, а более структурным. Например, есть алгоритм, который перебирает все перестаовки в лексикографическом порядке, при котором можно проводить отсечение на префиксах, например, если мы получили префикс D=0, E=1, то очевидно что Y=1 и в общем-то нет смысла строить все перестановки дальше. Дуальные методы (к которым относится метод циклических перестановок) очень плохо стправляется с такой ситацией, когда можно пропустить большой блок перестановок.

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

Интересный алгоритм, спасибо за статью.

Как Вы уже упомянули даже для малых n — количество перестановок огромно. Какие есть варианты параллелизации данного алгоритма? Могут ли подобные вычисления выполняться несколькими ядрами/ компьютерами независимо? Какой необходимый оверхед на синхронизацию потоков/процессов , если применить многопоточность,

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

Спасибо за статью. Алгоритм правда красивый.
Но как вы оцениваете его временую сложность? Выглядит что нужно сделать n — 1 дополнительную операцию left_shift для массива длиной n. А сам left_shift это уже O(k) в данной имплементации.

Спасибо за высокую оценку моей работы. Попробую оценить сложность этого алгоритма. Для получения одной перестановки точно понадобится один сдвиг при k = n. Таким образом стоимость такого сдвига уже O(n), если на последнем индексе стоит элемент равный индексу то понадобиться , несколько вспомогательных сдвигов размером k,k-1,...1 (опять же крайний случай остановки алгоритма) в таком случае это уже O(k^2) если вспомнить что в алгоритме (пункт 2 ) всегда переносим k = n, то в этом случае получим O(n^2). В итоге стоимость получения одной перестановки лежит между линейной и квадратичной, но большую часть алгоритма она линейна (квадратичное только условие завершения). Но, это только для одной перестановки, а их полное количество факториально. Т.е. время для генерации всех перестановок будет пропорционально выражению n!*n. Что по сути даст все равно факториальную сложность O(n!).

как эта хрень сюда попала ? это учат в школе на паскале. За что человека заставили писать на паскале ?

Точно! и макак кошками назвали! жесть!

За что человека заставили писать на паскале ?

«Ты что, дальтоник, скрипач?» (tm)

Підписатись на коментарі