Булеан можно рассматривать как объединение всевозможных сочетаний, построенных из элементов множества Поэтому генерация множества может быть сведена к генерации булеана и выбору из него всех подмножеств с мощностью
(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: