Генерация размещений

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

Лекция 4

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

На рис. 1 представлена схема построения множества размещений из элементов множества

Генерация размещений осуществляется в три этапа:

1. Для множества формируется множество всех сочетаний по три элемента. Таких сочетаний будет

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

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

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

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

На последнем этапе формируется множество всех перестановок элементов множества Элементы множества на рис. 1 отображены в крайнем справа столбце.

Рис.1. Схема генерации размещений

Пример. Имеется множество из 4-х элементов. Необходимо получить все возможные размещения по 2 элемента. Сначала получаем множество всех подмножеств – 16. Затем берем все сочетания по 2 – их будет 6, а потом получившиеся сочетания переставляем – их получается 12.

Реализация генератора размещений на языке С++

На рис. 2 и 3 представлена реализация программы генератора перестановок, а на рис. 4 и 5 приведен пример построения множества размещений с помощью этой программы и результат выполнения программы соответственно.

// Combi.h #pragma once namespace combi { struct accomodation// генератор размещений { short n,// количество элементов исходного множества m,// количество элементов в размещении *sset;// массив индесов текущего размещения xcombination *cgen;// указатель на генератор сочетаний permutation *pgen;// указатель на генератор перестановок accomodation(short n = 1, short m = 1);// конструктор void reset();// сбросить генератор, начать сначала short getfirst();// сформировать первый массив индексов short getnext();// сформировать следующий массив индексов short ntx(short i);// получить i-й элемент массива индексов unsigned __int64 na;// номер размещения 0,..., count()-1 unsigned __int64 count() const;// общее количество размещений }; } };

Рис.2. Шаблон структуры генератора размещений

// Combi.cpp #include "stdafx.h" #include "Combi.h" namespace combi { accomodation::accomodation (short n, short m) { this->n = n; this->m = m; this->cgen = new xcombination(n,m); this->pgen = new permutation(m); this->sset = new short[m]; this->reset(); } void accomodation::reset() { this->na = 0; this->cgen->reset(); this->pgen->reset(); this->cgen->getfirst(); }; short accomodation::getfirst() { short rc = (this->n >= this->m)?this->m:-1; if (rc > 0) { for (int i = 0; i <= this->m; i++) this->sset[i] = this->cgen->sset[this->pgen->ntx(i)]; }; return rc; }; short accomodation::getnext() { short rc; this->na++; if ((this->pgen->getnext())> 0) rc = this->getfirst(); else if ((rc = this->cgen->getnext())> 0) {this->pgen->reset(); rc = this->getfirst();}; return rc; }; short accomodation::ntx(short i) { return this->sset[i]; }; unsigned __int64 fact(unsigned __int64 x){ return (x == 0)?1:(x*fact(x-1));}; unsigned __int64 accomodation::count() const { return (this->n >= this->m)? fact(this->n)/fact(this->n - this->m):0; }; } };

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

// --- main #include "stdafx.h" #include <iostream> #include <iomanip> #include "Combi.h" #define N (sizeof(AA)/2) #define M 3 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 < N; i++) std::cout<<AA[i]<<((i< N-1)?", ":" "); std::cout<<"}"; std::cout<<std::endl<<"Генерация размещений из "<< N <<" по "<<M; combi::accomodation s(N,M); int n = s.getfirst(); while (n >= 0) { std::cout<<std::endl<<std::setw(2)<<s.na<<": { "; for (int i = 0; i < 3; i++) std::cout<<AA[s.ntx(i)]<<((i< n-1)?", ":" "); std::cout<<"}"; n = s.getnext(); }; std::cout<<std::endl<<"всего: "<<s.count()<<std::endl; system("pause"); return 0; }

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

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

Как и в предыдущих случаях, генератор размещений тоже реализован в виде структуры. Структура accomodation имеет один конструктор. С помощью двух параметров конструктору передается размерность исходного множества (параметр n) и размерность генерируемых размещений (параметр m).

В своей работе генератор размещений использует два встроенных генератора: сочетаний (указатель cgen) и перестановок (указатель pgen).

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

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

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

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

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

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