Генерация сочетаний

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

(2)

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

25:

Рис.14. Схема генерации сочетаний на основе множества всех подмножеств

26:

Рассмотрим еще один пример. Имеется множество всех подмножеств:. Всего подмножеств 16. Требуется найти все сочетания по три.

Порядковый номер	Запись в двоичном коде	Запись подмножеств в общем виде	Требуемые сочетания по три

27-29:

На рис. 15 и 16 представлена реализация генератора сочетаний на языке С++. Генератор реализован в виде структуры xcombination.

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

Рис. 15. Шаблон структуры генератора сочетаний

// Combi.cpp #include "stdafx.h" #include "Combi.h" #include <algorithm> namespace combi { xcombination::xcombination (short n, short m) { this->n = n; this->m = m; this->sset = new short[m+2]; this->reset(); } void xcombination::reset()// сбросить генератор, начать сначала { this->nc = 0; for(int i = 0; i < this->m; i++) this->sset[i] = i; this->sset[m] = this->n; this->sset[m+1] = 0; }; short xcombination::getfirst() { return (this->n >= this->m)?this->m:-1; }; short xcombination::getnext()// сформировать следующий массив индексов { short rc = getfirst(); if (rc > 0) { short j; for (j = 0; this->sset[j]+1 == this->sset[j+1]; ++j) this->sset[j] = j; if (j >= this->m) rc = -1; else { this->sset[j]++; this->nc++; }; } return rc; }; short xcombination::ntx(short i) { return this->sset[i]; }; unsigned __int64 fact(unsigned __int64 x){return(x == 0)?1:(x*fact(x-1));}; unsigned __int64 xcombination::count() const { return (this->n >= this->m)? fact(this->n)/(fact(this->n-this->m)*fact(this->m)):0; }; };

Рис. 16. Реализация функций генератора сочетаний

Структура xcombination имеет один конструктор с двумя параметрами. Первый параметр определяет количество элементов в исходном множестве, второй – количество элементов в генерируемых сочетаниях.

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

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

Функция getfirst (рис. 16) не имеет параметров и предназначена для проверки корректности параметров, заданных в конструкторе. Эта функция не формирует массива индексов, как это происходило в структуре subset (генератор множества всех подмножеств). В основном она существует для унификации интерфейсов всех генераторов. Функция возвращает отрицательное значение, если параметры генератора заданы неверно.

Функция getnext формирует массив индексов следующего сочетания и увеличивает значение переменной nc на единицу. При каждом вызове функции для текущего массива индексов вычисляется новое значение j -индекса и, если оно не превышает m, строится новый массив индексов. При достижении j -индексом значения, равного или превышающего m, функция возвращает отрицательное значение, в других случаях возвращается положительное значение.

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

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

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

30-32:

Пример использования генератора сочетаний и результат выполнения программы.

// Main #include "stdafx.h" #include <iostream> #include "Combi.h" int _tmain(int argc, _TCHAR* argv[]) { setlocale(LC_ALL, "rus"); char AA[][2]= {"A", "B", "C", "D", "E"}; 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::xcombination xc(sizeof(AA)/2, 3); std::cout<<"из "<<xc.n<< " по "<< xc.m; int n = xc.getfirst(); while (n >= 0) { std::cout<<std::endl<<xc.nc <<": { "; for (int i = 0; i < n; i++) std::cout<<AA[xc.ntx(i)]<<((i< n-1)?", ":" "); std::cout<<"}"; n = xc.getnext(); }; std::cout<<std::endl<<"всего: " << xc.count()<<std::endl; system("pause"); return 0; }

Рис. 17. Пример применения генератора сочетаний

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

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

Генерация сочетаний начинается функцией getfirst. Если функция возвращает положительное значение, то сформирован индекс массивов первого сочетания. Массив индексов каждого следующего сочетания формируется функцией getnext. Выбор элементов исходного массива осуществляется с помощью функции ntx. Признаком завершения цикла генерации является отрицательное значение функции getnext.

33:

Дата добавления: 2014-01-20