Цель занятия:
Целью занятия является практическое изучение объектно-ориентированной обработки списковых структур данных на примере применения двусвязного списка для систематического перебора перестановок конечного множества элементов с помощью алгоритма вращения, который является классическим алгоритмом прикладной комбинаторики.

Формулировка задания:
Разработать программу permut систематического перебора перестановок символов, представленных в форме двунаправленного списка элементов, используя алгоритм вращения.

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

Результат: поток стандартного вывода всех перестановок символов исходной строки.

Понятие перестановки

Перестановка - упорядоченная выборка элементов конечного множества, в которой все элементы различны. Каждому элементу перестановки поставлено в соответствие определенное натуральное число - номер элемента. В общем случае перестановка n-элементного множества (n-перестановка) обозначается следующим образом:


где Si - элемент исходного множества, расположенный в i-й позиции перестановки.

Конечное множество из n элементов можно упорядочить n! различными способами, получив n! перестановок, которые отличаются только порядком элементов. Например, для множества из 3-х элементов:


можно построить 3! (6) перестановок:


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

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

Алгоритм вращения основан на организации циклического сдвига элементов перестановки. Естественный способ перечисления перестановок циклическим сдвигом состоит в том, что начав с некоторой исходной перестановки, нужно последовательно сдвигать по циклу на 1 позицию влево все n элементов. При каждом сдвиге 1-й элемент текущей перестановки перемещается на последнее место без изменения взаимного расположения остальных элементов, образуя новую перестановку. Такая организация цикла сдвига называется вращением.

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

Когда в результате очередного вращения образуется ранее порожденная перестановка, нужно исследовать возможность построить оригинальную перестановку, применяя вращение последовательно для первых j=n-1, n-2,...,2 элементов, при фиксированном положении (n-j) хвостовых элементов. Если локальное вращение 1<j<n элементов порождает оригинальную перестановку, следует продолжить вращение циклическим сдвигом всех n элементов. В противном случае (j=1), перебор считается завершенным, т. к. перечислены все n! перестановок.

Рассмотренный процесс систематического перечисления перестановок циклическим сдвигом называется алгоритмом вращения.

Формальную схему алгоритма вращения иллюстрирует следующий псевдокод.

P=(P1,...,Pi,...,Pn)// исходная перестановка 

S=(S1,...,Si,...,Sn)// текущая перестановка 

S<--- P // копирование исходной перестановки 

j <---0 // диапазон сдвига 

while (j!=1) { 

J<--- n // установить максимальный диапазон сдвига 

S<<1 // циклический сдвиг влево на 1 элемент 

while (Sj=Pj AND j!=1) { 

j<--- j-1 // уменьшить на 1 диапазон сдвига 

S<<1 // локальный сдвиг влево на 1 элемент 

} 

printS // печать текущей перестановки 

} 

return 

Двусвязные списки

Для хранения и обработки перестановок алгоритмом вращения удобно использовать 2-связные (двунаправленные) линейные списки, записи которых связаны посредством пары указателей, хранимых в адресных полях записей списка. Логическую структуру 2-связного списка иллюстрирует следующая диаграмма

Рис. 1.  диаграмма 2-связного списка

В каждой записи поле prev содержит адрес предыдущей записи, поле - next - адрес последующей записи, а data обозначает информационные поля. Для доступа к списку могут быть использованы адреса начальной (start), конечной (end) и текущей (this) записей списка. Индикатором начальной и конечной записей являются нулевые (NULL) значения адресных полей Start и end, соответственно.

Любая функциональная обработка списка строится на основе процедур модификации и просмотра. Процедуры модификации должны обеспечивать вставки и исключение записей списка. Частным случаем процедур вставки и исключения являются процедуры добавить и удалить начальную или конечную запись списка. Следующая диаграмма иллюстрирует процедуру вставки новой записи Z после записи Y (или перед записью X)

Рис. 2.  

Следующая диаграмма иллюстрирует процедуру исключения текущей записи this.

Рис. 3.  

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

Рис. 4.  


Частным случаем смещения указателя текущей записи является переход к соседней предыдущей или последующей записи (смещение на 1 позицию), а также нефиксированный переход к начальной или конечной записям списка, который позволяет принудительно инициализировать указатели start и end после модификаций в начале и конце списка.

Объектное программирование списковых перестановок

Для организации объектно-ориентированной обработки перестановок, реализованных на основе списковых структур, целесообразно построить базовый класс записей 2-связного списка (lass Dlink) и производный от него класс перестановок (class Permit).

Базовый класс Dlink должен включать универсальные компоненты. Компоненты-данные класса Dlink должны обеспечивать двунаправленную защищенную (protected) связь записей списка посредством 2-х адресных полей Dlink*prev и Dlink*next, которые содержат адреса предыдущей и последующей записей списка, соответственно. Универсальную обработку записей списка должны обеспечивать общедоступные (public) компонентные методы класса Dlink:

void after(Dlink*) - вставить адресуемую запись в список после текущей записи this;

void before(Dlink*) - вставить адресуемую запись в список перед текущей записью this;

Dlink*incr( ) - возвращает адрес следующей после текущей (this) записи списка;

Dlink*decr( ) - возвращает адрес записи перед текущей записью (this);

Dlink*append (Dlink*) - добавляет адрес записи, отстоящей от текущей записи (this) на заданное число позиций в направлении начала или конца списка, причем знак аргумента определяет направление поиска.

Dlink*seek (int) - найти адрес записи, отстоящей от текущей записи (this) на заданное число позиций в направлении начала или конца списка, причем знак аргумента определяет направление поиска.

Класс Dlink должен содержать конструктор без аргументов, который инициализирует нулевым значением (NULL) адресные поля новой записи списка:

Производный класс Permut должен наследовать компонентные данные и методы базового класса Dlink. Его декларация должна иметь вид:

class Prmut: public Dlink { ... };

Кроме наследуемых компонент базового класса, производный класс Permut должен содержать собственные компоненты, необходимые для постановочной обработки списка. Защищенные ( protected) компоненты-данные класса Permut образуют информационные поля записей списка, определяющие позицию элемента в исходной перестановке (unsigned pos) и символическое алфавитно-цифровое обозначение элемента (char name). Общедоступную часть класса Permut составляют методы подготовки исходной перестановки и её обработки алгоритмом вращения. Эти проблемы решают компонентные методы allocate и rotate. Исходная перестановка элементов в классе Prmut должна формироваться статическим компонентным методом allocate, который имеет следующий прототип:

Static Permut*allocate(char*);

Эта функция должна возвращать адрес начала списка элементов перестановки, обозначения которых передаются ей как аргумент. Компонентный метод allocate должен задаваться статической функцией, чтобы его можно было вызвать при отсутствии объектов класса Permut, например, в следующем контексте:

Permut*p=Permut::allocate(”a b c d” );

Формирование исходной перестановки должно сопровождаться проверкой отсутствия элементов с одинаковыми или некорректными именами. Эту проверку должен обеспечивать компонентный предикат:

int scan (Permut*);

Предикат scan должен вызываться в теле метода allocate для каждого нового элемента формируемой перестановки, стартовый адрес списка элементов которой передается методу scan в качестве аргумента для сканирования повторов имён. Код возврата метода scan определяет возможность создания и включения в перестановку нового элемента с проверенным обозначением. Для обращения к функции scan нужно создать временный автоматический объект класса Permut в блоке функции allocate. Этот временный объект имеет смысл заготовки (dummy), по которой проверяется правильность обозначения нового элемента перестановки. При положительном результате проверки новый элемент перестановки образуется конструктором копирования-инициализации (c-i конструктор) класса Permut, который следует определить следующим образом:

Permut( Permut&dummy):Dlink(){ 

name=dummy.name; pos=dummy.pos; 

}

Этот конструктор создает новый объект ( элемент перестановки), копируя информационные поля ( компоненты-данные) из проверенной заготовки dummy. Адресные поля инициализируют конструктор базового класса Dlink(). Вызов c-i конструктора следует поручить оператору new, который возвратит адрес нового элемента перестановки в следующей транскрипции:

Permut*p=new Permut(dummy);

Новый элемент перестановки можно добавить в начало списка уже существующих элементов методом append, который наследуется от базового класса. Все рассмотренные действия в теле функции allocate нужно выполнить для каждого символа строки её аргумента. После завершения формирования исходной перестановки адрес списка её элементов следует возвратить в блок функции, которая вызывает метод allocate, например, функции main().

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

void print() - печать текущей перестановки в потоке стандартного вывода;

Permut*locate(unsigned) - определяет адрес последнего сдвигаемого элемента в заданном как аргумент диапазона вращения;

unsigned permlen() - определяет число элементов перестановки.

В заключение обзора методов класса permut следует отметить целесообразность перегрузки наследованных методов базового класса Dlink, которые имеют адресный код возврата.

Например, базовый метод:

Dlink*Dlink::decr() {return prev;}
можно перегрузить в производном классе Permut следующим образом:

Dlink*Dlink::decr() { 

return ((Permut*)Dlink::decr()); 

}//Permut::decr

Это обеспечивает корректное преобразование типа в случае присваивания возврата этой функции указателю на производный класс Permut, например, в следующем фрагменте C++ кода:

Permut d; 

Permut*p=d.decr(); // перегруженный метод decr 

Преобразование типа в этом контексте необходимо т.к. синтаксис языка С++ запрещает присваивать указатель базового класса ( в данном случае Dlink) указателю производного класса ( в данном случае Permut). Эта проблема могла быть решена путем явного преобразования типа без перегрузки наследуемых методов базового класса в производный классе, например, следующим образом:

Permut d; 

Permut*p=(Permut*)d.decr(); // метод decr не перегружен 

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

Контрольные задания.

  1. Дополнить класс перестановок Permut методами формирования случайных перестановок на основе случайных транспозиций каждого элемента Si c элементами Si,..., Si-1, i=n, n-1, ...,2
  2. Построить класс двусвязного списка из классов односвязных списков на основе аппарата множественного наследования.
  3. Построить класс записей двусвязного списка как контейнерный класс, содержащий классы записей односвязных списков.
  4. Реализовать программу permut, используя базовый класс односвязного списка, рассмотрев вариант кольцевого списка и списка со сторожем.