Нерекурсивный алгоритм генерации перестановок
- понедельник, 26 января 2015 г. в 02:11:24
http://habrahabr.ru/post/248493/
Предлагаемый ниже нерекурсивный алгоритм несколько отличается от изложенных в книге Липского [1] и обнаруженных мной в русскоязычном сегменте интернета. Надеюсь будет интересно.
Кратко постановка задачи. Имеется множество размерности N. Необходимо получить все N! возможных перестановок.
Далее, для простоты, используем в качестве множества целые числа (1..N). Вместо чисел можно использовать любые объекты, т.к. операций сравнения элементов множества в алгоритме нет.
Для хранения промежуточных данных сформируем структуру данных следующего вида:
и заполним ее первоначальными значениями
Номер элемента в массиве masiv будем далее называть уровнем.
В список первого уровня заносим все элементы множества. На первом уровне размерность списка равна N и сам список не изменяется по всему ходу выполнения алгоритма. При первичном заполнении все указатели в массиве устанавливаются на первый элемент в списке.
На каждом следующем уровне его список формируется на основании списка предыдущего уровня, но без одного элемента, который помечен указателем. На предпоследнем уровне (N-2) список содержит три элемента. На последнем уровне (N-1) список содержит два элемента. Список нижнего уровня формируется как список предыдущего уровня без элемента, на который указывает указатель предыдущего уровня.
В результате первичного заполнения получены две первых перестановки.Это общий массив сформированный на верхних уровнях ( 1… (N-2)) из элементов списка на которые указывают указатели.
и из списка последнего уровня- две пары элементов в разном порядке ( два хвостика 1 2 и 2 1)
Все дальнейшие перестановки формируются также, всегда с предпоследнего уровня (N-2),
Порядок получения последующих перестановок состоит в том, что находясь на предпоследнем уровне (N-2) и сформировав две перестановки пытаемся увеличить указатель выбранного элемента на 1.
Если это возможно, то на последнем уровне меняем список и повторяемся.
Если на предпоследнем уровне увеличить указатель не удается (перебраны все возможные варианты ), то поднимаемся до уровня на котором увеличение указателя (перемещение вправо) возможно. Условие окончания работы алгоритма — указатель на первом уровне выходит за N.
После сдвига указателя вправо меняем список под ним и двигаемся вниз до предпоследнего уровня (N-2) также обновляя списки и устанавливая указатели выбранного элемента в 1.
Более наглядно и понятно работа алгоритма представлена на рисунке ниже ( для размерности множества N =5). Номер на рисунке соответствует уровню в описании. Возможно даже, что кроме рисунка для понимания алгоритма ничего и не надо.
Конечно, при реализации алгоритма можно было использовать и обычный двухмерный массив, тем более что для небольших N выигрыш объема памяти ничего не дает, а на больших N мы можем не дождаться окончания работы алгоритма.
Один из способов реализации алгоритма на VBA ниже. Для его запуска можно создать книгу Excel с макросами, создать модуль на вкладке разработчик VB и скопировать текст в модуль. После запуска generate() на Лист1 будут выведены все перестановки.
Ссылки:
[1] В.Липский. Комбинаторика для программистов. -Москва, издательство Мир, 1988.
Предлагаемый ниже нерекурсивный алгоритм несколько отличается от изложенных в книге Липского [1] и обнаруженных мной в русскоязычном сегменте интернета. Надеюсь будет интересно.
Кратко постановка задачи. Имеется множество размерности N. Необходимо получить все N! возможных перестановок.
Далее, для простоты, используем в качестве множества целые числа (1..N). Вместо чисел можно использовать любые объекты, т.к. операций сравнения элементов множества в алгоритме нет.
Для хранения промежуточных данных сформируем структуру данных следующего вида:
type dtree
ukaz as integer ' номер выбранного элемента в списке
spisok() as integer ' список доступных значений
end type
и заполним ее первоначальными значениями
Dim masiv(N-) As dtree ' размерность массива = N-1
For ii = 1 To N - 1
masiv(ii).ukaz = 1
ReDim masiv(ii).spisok(N + 1 - ii) ' устанавливаем размерность списка
For kk = 1 To (N + 1 - ii)
masiv(ii).spisok(kk) = kk + ii - 1
Next
Next
Номер элемента в массиве masiv будем далее называть уровнем.
В список первого уровня заносим все элементы множества. На первом уровне размерность списка равна N и сам список не изменяется по всему ходу выполнения алгоритма. При первичном заполнении все указатели в массиве устанавливаются на первый элемент в списке.
На каждом следующем уровне его список формируется на основании списка предыдущего уровня, но без одного элемента, который помечен указателем. На предпоследнем уровне (N-2) список содержит три элемента. На последнем уровне (N-1) список содержит два элемента. Список нижнего уровня формируется как список предыдущего уровня без элемента, на который указывает указатель предыдущего уровня.
В результате первичного заполнения получены две первых перестановки.Это общий массив сформированный на верхних уровнях ( 1… (N-2)) из элементов списка на которые указывают указатели.
For ii = 1 To N-2
massiv(ii).spisok(ukaz)
Next
и из списка последнего уровня- две пары элементов в разном порядке ( два хвостика 1 2 и 2 1)
+ massiv(N-1).spisok(1) + massiv(N-1).spisok(2)
+ massiv(N-1).spisok(2) + massiv(N-1).spisok(1)
Все дальнейшие перестановки формируются также, всегда с предпоследнего уровня (N-2),
Порядок получения последующих перестановок состоит в том, что находясь на предпоследнем уровне (N-2) и сформировав две перестановки пытаемся увеличить указатель выбранного элемента на 1.
Если это возможно, то на последнем уровне меняем список и повторяемся.
Если на предпоследнем уровне увеличить указатель не удается (перебраны все возможные варианты ), то поднимаемся до уровня на котором увеличение указателя (перемещение вправо) возможно. Условие окончания работы алгоритма — указатель на первом уровне выходит за N.
После сдвига указателя вправо меняем список под ним и двигаемся вниз до предпоследнего уровня (N-2) также обновляя списки и устанавливая указатели выбранного элемента в 1.
Более наглядно и понятно работа алгоритма представлена на рисунке ниже ( для размерности множества N =5). Номер на рисунке соответствует уровню в описании. Возможно даже, что кроме рисунка для понимания алгоритма ничего и не надо.
Конечно, при реализации алгоритма можно было использовать и обычный двухмерный массив, тем более что для небольших N выигрыш объема памяти ничего не дает, а на больших N мы можем не дождаться окончания работы алгоритма.
Один из способов реализации алгоритма на VBA ниже. Для его запуска можно создать книгу Excel с макросами, создать модуль на вкладке разработчик VB и скопировать текст в модуль. После запуска generate() на Лист1 будут выведены все перестановки.
VBA для Excel
Option Explicit
Type dtree
tek_elem_ukaz As Integer
spisok() As Integer
End Type
Dim masiv() As dtree
Dim start_print As Integer
Dim N As Integer
Sub generate()
Dim ii As Integer, kk As Integer, jj As Integer
Dim uroven As Integer
Лист1.Cells.Clear
N = 5
start_print = 1
ReDim masiv(N - 1)
' первичное заполнение
For ii = 1 To N - 1
masiv(ii).tek_elem_ukaz = 1
ReDim masiv(ii).spisok(N + 1 - ii)
For kk = 1 To (N + 1 - ii)
masiv(ii).spisok(kk) = kk + ii - 1
Next
Next
uroven = N - 2
Do
' результат
Call print_rezult(uroven)
' на последнем уровне можно сдвинуться вправо
If masiv(uroven).tek_elem_ukaz <= (N - uroven) Then
' делаем шаг вправо
' меняем тек элемент
masiv(uroven).tek_elem_ukaz = masiv(uroven).tek_elem_ukaz + 1
' меняем массив снизу
Call zap_niz(uroven)
Else
' делаем шаг вверх до первого уровня, где можно сдвинуться вправо
Do While uroven > 1 And masiv(uroven).tek_elem_ukaz > (N - uroven)
uroven = uroven - 1
Loop
If uroven = 1 And masiv(1).tek_elem_ukaz = N Then
MsgBox "stop calc"
Exit Sub ' напечатали все
End If
' делаем шаг вправо на первом снизу доступном уровне
masiv(uroven).tek_elem_ukaz = masiv(uroven).tek_elem_ukaz + 1
Call zap_niz(uroven)
' заполнение нижних уровней
Do While uroven < N - 2
uroven = uroven + 1
masiv(uroven + 1).tek_elem_ukaz = 1
' меняем массив снизу
For kk = 2 To N - uroven + 1
masiv(uroven + 1).spisok(kk - 1) = masiv(uroven).spisok(kk)
Next
Loop
End If
Loop
End Sub
Sub print_rezult(ukaz As Integer)
Dim ii As Integer
For ii = 1 To ukaz
With masiv(ii)
Лист1.Cells(start_print, ii) = .spisok(.tek_elem_ukaz)
Лист1.Cells(start_print + 1, ii) = .spisok(.tek_elem_ukaz)
End With
Next
With masiv(ukaz + 1)
Лист1.Cells(start_print, ukaz + 1) = .spisok(1)
Лист1.Cells(start_print, ukaz + 2) = .spisok(2)
start_print = start_print + 1
Лист1.Cells(start_print, ukaz + 1) = .spisok(2)
Лист1.Cells(start_print, ukaz + 2) = .spisok(1)
start_print = start_print + 1
End With
End Sub
Sub zap_niz(ukaz As Integer)
' заполнение нижнего уровня
Dim ii As Integer, wsp1 As Integer
' меняем тек элемент
wsp1 = masiv(ukaz).tek_elem_ukaz
masiv(ukaz + 1).tek_elem_ukaz = 1
' меняем массив снизу
For ii = 1 To wsp1 - 1
masiv(ukaz + 1).spisok(ii) = masiv(ukaz).spisok(ii)
Next
For ii = wsp1 + 1 To N - ukaz + 1
masiv(ukaz + 1).spisok(ii - 1) = masiv(ukaz).spisok(ii)
Next
End Sub
Ссылки:
[1] В.Липский. Комбинаторика для программистов. -Москва, издательство Мир, 1988.