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

КОМБИНАТОРНЫЕ МЕТОДЫ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ

Лекция 3

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

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

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

Построение множества всех перестановок с помощью алгоритма Джонсона – Троттера сводится к следующей процедуре:

1. Построить первую перестановку. Первая перестановка – это последовательность всех элементов множества перечисленных в порядке возрастания. Стрелки всех элементов последовательности направлены влево.

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

3. Поменять местами наибольший мобильный элемент и элемент, на который указывает стрелка наибольшего мобильного элемента.

4. Найти все элементы, большие, чем мобильный элемент (если они есть) и изменить их стрелки на противоположное направление.

5. Перейти к пункту 2.

Схема алгоритма генерации множества всех перестановок множества приведена на рис. 1.

Рис. 1. Схема работы алгоритма Джонсона – Троттера

Второй слева столбец на рис. 1 – массив индексов, генерируемый с помощью алгоритма Джонсона – Троттера. Каждый массив индексов является одной из перестановок элементов множества. Количество массивов составляет:

Самый правый столбец (обозначен) – множество всех перестановок элементов Перестановки формируются как результат индексации массива

Реализация генератора перестановок на языке C++

На рис. 2 и 3 представлена программная реализация генератора перестановок, а на рис. 4 и 5 приведен пример его применения.

// Combi.h #pragma once namespace combi { struct permutation// генератор перестановок { const static bool L = true;// левая стрелка const static bool R = false;// правая стрелка short n,// количество элементов исходного множества *sset;// массив индексов текущей перестановки bool *dart;// массив стрелок (левых-L и правых-R) permutation (short n = 1);// конструктор (количество элементов исходного множества) void reset();// сбросить генератор, начать сначала __int64 getfirst();// сформировать первый массив индексов __int64 getnext();// сформировать случайный массив индексов short ntx(short i);// получить i-й элемент масива индексов unsigned __int64 np;// номер перествновки 0,... count()-1 unsigned __int64 count() const;// вычислить общее кол. перестановок }; };

Рис. 2. Шаблон структуры генератора перестановок

// Combi.cpp #include "stdafx.h" #include "Combi.h" #include <algorithm> #define NINF ((short)0x8000) namespace combi { permutation::permutation(short n) { this->n = n; this->sset = new short[n]; this->dart = new bool[n]; this->reset(); }; void permutation::reset() { this->getfirst(); }; __int64 permutation::getfirst() { this->np = 0; for (int i = 0; i < this->n; i++) {this->sset[i] = i; this->dart[i] = L;}; return (this->n > 0)?this->np:-1; }; __int64 permutation::getnext() // { __int64 rc = - 1; short maxm = NINF, idx = -1; for(int i = 0; i < this->n; i++) { if (i > 0 && this->dart[i] == L && this->sset[i] > this->sset[i-1] && maxm < this->sset[i]) maxm = this->sset[idx = i]; if (i < (this->n-1)&& this->dart[i] == R && this->sset[i] > this->sset[i+1]&& maxm < this->sset[i]) maxm = this->sset[idx = i]; }; if (idx >= 0) { std::swap(this->sset[idx], this->sset[idx+(this->dart[idx]== L?-1:1)]); std::swap(this->dart[idx], this->dart[idx+(this->dart[idx]== L?-1:1)]); for (int i = 0; i < this->n; i++) if (this->sset[i] > maxm) this->dart[i] =!this->dart[i]; rc = ++this->np; } return rc; }; short permutation::ntx(short i){return this->sset[i];}; unsigned __int64 fact(unsigned __int64 x){return (x == 0)?1:(x*fact(x-1));}; unsigned __int64 permutation::count() const {return fact(this->n); }; }

Рис. 3. Реализация функций генератора перестановок

// --- Main #include "stdafx.h" #include <iostream> #include "Combi.h" #include <iomanip> int _tmain(int argc, _TCHAR* argv[]) { setlocale(LC_ALL, "rus"); char AA[][2]= {"A", "B", "C", "D"}; std::cout<<std::endl<<" --- Генератор перестановок ---"; std::cout<<std::endl<<"Исходное множество: "; std::cout<<"{ "; for (int i = 0; i < sizeof(AA)/2; i++) std::cout<<AA[i]<<((i< sizeof(AA)/2-1)?", ":" "); std::cout<<"}"; std::cout<<std::endl<<"Генерация перестановок "; combi::permutation p(sizeof(AA)/2); __int64 n = p.getfirst(); while (n >= 0) { std::cout<<std::endl<<std::setw(4)<< p.np <<": { "; for (int i = 0; i < p.n; i++) std::cout<<AA[p.ntx(i)]<<((i< p.n-1)?", ":" "); std::cout<<"}"; n = p.getnext(); }; std::cout<<std::endl<<"всего: " << p.count()<<std::endl; system("pause"); return 0; }

Рис. 4. Пример применения генератора перестановок

Рис. 5. Результат выполнения программы, представленной на рис. 4

Генератор реализован в виде структуры permutation. Структураимеет один конструктор. С помощью параметра конструктору передается размерность исходного множества.

Состояние генератора определяется значениями четырех переменных: n (количество элементов в исходном множестве), sset (указатель на массив индексов), dart (указатель на массив стрелок), np (номер текущей перестановки).Всепеременные инициализируются в конструкторе. Значение np увеличивается на единицу после генерации очередной перестановки, значение остальных переменных остается неизменным. Элементы массивов sset и dart меняются при каждом цикле работы генератора в соответствии с алгоритмом Джонсона –Троттера.

Кроме конструктора структура permutation содержит еще пять функций.

Функция getfirst (см.рис. 4) не имеет параметров и предназначена для формирования первой перестановки, которая представляет собой упорядоченную последовательность n (переменная структуры на рис. 3) неотрицательных целых чисел (см. рис. 1).

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

Функция getnext формирует массив индексов следующей перестановки и увеличивает значение переменной np на единицу. При каждом вызове функции в массиве sset отыскивается максимальный мобильный элемент и элемент, на который указывает его стрелка, эти элементы меняются местами. Если существуют элементы sset,большие, чем найденный мобильный, то соответствующие им стрелки инвертируются.

Функция ntx возвращает значение элемента массива индексов по индексу этого элемента и служит для сокращения записи при переборе элементов массива.

Функция count вычисляет и возвращает общее количество перестановок n элементов множества.