Генерация перестановок и комбинаций в буфере произвольного размера
ОГЛАВЛЕНИЕ
Статья о быстрой генерации всевозможных перестановок и комбинаций новым и простым образом
• Скачать демонстрационный проект- 52.6 Кб
• Скачать исходники - 5 Кб
Введение
В данной статье объясняется алгоритм, способный генерировать перестановки и комбинации без использования классических математических понятий. Программно вводится многоразмерный буфер, чтобы алгоритм мог эффективно работать со сгенерированной последовательностью любого размера. Все это инкапсулировано в класс C++, названный CStrCombin.
Класс CStrCombin удобен во многих сферах, таких как математические вычисления, программы-генераторы паролей, генераторы слов. Тестирование этого класса в демонстрационной программе дало хорошие результаты. Сравнение времени выполнения этого алгоритма с аналогичными по функциям программами показало, что использование CStrCombin намного быстрее.
Предпосылки
• Перестановки (компоновки) без повторов
Перестановка – компоновка объектов в разных порядках. Порядок компоновок важен. Обозначение для перестановки - nPr. n – общее количество объектов (символов), а r – количество выбираемых объектов. r также называется количеством мест, которое может занимать сгенерированная последовательность выбранных объектов. Всегда имеется n>=r.
Рассмотрим пример:
Набор символов - {A,B,C,D} (n=4). Надо получить все компоновки r=3 из числа n=4. Итак, результат таков:
BCD, ACD, CBD, ABD, CAD, BAD, BDC, ADC, DBC, ABC, DAC, BAC,
CDB, ADB, DCB, ACB, DAB, CAB, CDA, BDA, DCA, BCA, DBA, CBA.
4P3= 24
• Перестановки с повторами
Вычисляются как nr. n может быть меньше r.
Рассмотрим пример:
Набор символов - {A,B,C,D} (n=4)
Надо получить все компоновки с повторами r=2 из числа n=4. Итак, результат таков:
DD, CD, BD, AD, DC, CC, BC, AC,
DB, CB, BB, AB, DA, CA, BA, AA.
42 = 16
• Комбинации
Комбинация – неупорядоченный набор уникальных элементов. Если дан S, набор всевозможных уникальных элементов, то комбинация является подгруппой элементов из S. Порядок элементов в комбинации не важен (два списка с одними и теми же элементами в разных порядках считаются одной и той же комбинацией). Также элементы в комбинации не могут повторяться (каждый уникальный элемент появляется один раз); это часто называется "без дубликатов/повторов".
Рассмотрим пример:
Набор символов - {A,B,C,D} (n=4)
Надо получить все комбинации r=3 из числа n=4. Итак, результат таков:
BCD, ACD, ABD, ABC.
4C3= 4
Основы алгоритма
Исходная точка – набор символов, заданный пользователем. Кроме того, пользователь задает желаемое количество мест, которое займут комбинации/компоновки. Алгоритм умеет генерировать компоновки с/без повторов и комбинации. Первый шаг процесса одинаков для 3 возможных целей. На первом шаге каждому символу в наборе присваивается число, представляющее индекс в наборе. Это показано в примере ниже:
<small> набор | A 0 C 0 E F G 7 " J K L 9 N O , T R 7 ; U V # X Y Z ... @
---------- + ------------------------------------------------------------------------------------
индекс | 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10 11 12 13 14 15 16 17 18 19 ... FF</small>
Значение индекса – беззнаковое целое значение, занимающее 1 байт. Этот алгоритм поддерживает максимум 256 символов. Далее значения индекса всегда будут обрабатываться в шестнадцатеричном виде.
Для упрощения объяснения возьмем набор из 4 букв и 3 места. Получится такое распределение:
набор | A B C D +---+---+---+
---------- + ---------------Сгенерированная последовательность | ? | ? | ? |
индекс | 00 01 02 03 должна состоять из 3 мест +---+---+---+
| LSB RSB
LSB: левосторонний байт
RSB: правосторонний байт
Второй шаг заключается в инициализации механизма генерации. Здесь лежит главная идея алгоритма. Чтобы генерировать компоновки/комбинации, надо вычислить все числа между LSB LSB LSB и RSB RSB RSB. Это значит 00 00 00 и 03 03 03. Сделав это, надо помнить, что значения индекса являются просто заменой настоящих заданных символов. Так что число 00 00 00 автоматически ссылается на строку AAA, а 03 03 03 ссылается на DDD. Отсюда следует, что вычисленные числа, выпадающие между 00 00 00 и 03 03 03 и имеющие один или несколько элементов, не соответствующих одному из выбранных ранее индексов, не нужны при поиске компоновок/комбинаций.
Компоновки/комбинации выбираются путем следующих операций:
• Все компоновки с повторами являются собранными последовательностями
• Все компоновки без повторений являются собранными последовательностями, не имеющими повторяющихся элементов
• Все комбинации являются компоновками без повторов, в которых индексы элементов последовательности упорядочены
В следующих разделах будет рассмотрено, как создать класс CStrCombin, применяющий представленный алгоритм.
Определение CBuffer
Класс CBuffer определяется так:
class CBuffer
{
public:
int m_size; // размер беззнакового целочисленного буфера в байтах
unsigned char* m_buf; // буфер, в котором хранятся данные
CBuffer(int,int); // конструктор версии 1
CBuffer(int); // конструктор версии 2
~CBuffer(void);
void operator++ ();
bool operator< (CBuffer&);
bool operator== (CBuffer&);
bool operator<= (CBuffer&);
};
Инициализация CBuffer максимальным значением буфера
Конструктор версии 1 позволяет создать буфер, инициализированный точным значением. Это значение основано на целом числе, являющемся максимальным индексом в заданной коллекции символов.
Этот конструктор определен ниже:
CBuffer::CBuffer(int hex,int places) //инициализировать максимальным значением
{
m_size=places;
m_buf=new unsigned char[m_size];
for(int i=0;i<m_size;i++)
m_buf[i]=hex;
}
Заметьте, что на данные буфера указывает m_buf.
Инициализация CBuffer нулевым значением буфера
Для создания буфера, содержащего 0, используется конструктор 2:
CBuffer::CBuffer(int places)//инициализировать нулевой буфер
{
m_size=places;
m_buf=new unsigned char[m_size];
for(int i=0;i<m_size;i++)
m_buf[i]=0;
}
Подсчет чисел от 0 до заданного максимального значения
Это делается посредством оператора ++:
//увеличить значение CBuffer на 1
void CBuffer::operator++ ()
{
for(int i=0;i<m_size;i++)
{
if(m_buf[i]!=0xff)
{
m_buf[i]++;
return;
}
else
m_buf[i]=0;
}
throw "Переполнение буфера!"; //генерировать исключение при появлении ошибки
}
Функции сравнения
Сравнения между объектами CBuffer могут понадобиться, особенно для операции <=. Напишем соответствующий оператор. Для этого надо написать оператор < и оператор ==. Их будет вызывать оператор <=. Код имеет вид:
bool CBuffer::operator< (CBuffer& obj)
{ //obj и текущий объект должны иметь одинаковый m_size!
for(int i=m_size-1;i>=0;i--)
{
if(obj.m_buf[i]>m_buf[i])
return true;
else
if(obj.m_buf[i]<m_buf[i])
return false;
}
return false;
}
bool CBuffer::operator== (CBuffer& obj)
{ //obj и текущий объект должны иметь одинаковый m_size!
for(int i=m_size-1;i>=0;i--)
if(obj.m_buf[i]!=m_buf[i])
return false;
return true;
}
bool CBuffer::operator<= (CBuffer& obj)
{
if(*this<obj || *this==obj)
return true;
else
return false;
}
Очистка памяти
Перед уничтожением буфера удаляются данные, на которые указывает указатель:
CBuffer::~CBuffer(void)
{
delete []m_buf;
}
Теперь можно создать буфер любого размера. Эта работа будет использована в классе CStrCombin.
Определение CStrCombin
Класс CStrCombin определяется так:
class CStrCombin //разрешение 59.57 мкс в процессоре P4 3ГГц.
{
public:
struct stack_cell
{
unsigned char* buf;
struct stack_cell* prev;
};
private:
#define m_StrSize 256
//CStrCombin поддерживает максимальный набор из 256 символов,
//из которого строится генерируемая последовательность
int m_mode;
//combWithoutRep: генерирует комбинации без повторов ( n P r )
//combWithRep: генерирует комбинации с повторами ( n в степени r )
//combComb: генерирует комбинации с повторами ( n C r )
char m_str[m_StrSize+1]; //буфер для хранения символов набора
int m_places; // размер генерируемой последовательности в байтах
stack_cell* m_pHead;
//ссылается на верх стека, используемый для сохранения чисел в память
unsigned long long m_combNbr; //содержит количество найденных последовательностей
unsigned long long m_combTime; //содержит длительность обработки
public:
enum RepetitionMode
{
combWithoutRep=1, // режим nPr
combWithRep, // режим n в степени r
combComb // режим nCr
};
CStrCombin();
~CStrCombin();
void SetGenMode(int);
void SetGenStr(char*);
void SetGenPlaces(int);
void GenAndSaveCombToFile(char*);
void push(unsigned char*);
void pop(HANDLE);
unsigned long long GetCombFoundNbr();
unsigned long long GetCombTime();
};
В следующих разделах рассматривается, как использовать разные члены класса для генерации комбинаций/компоновок.
Инициализация CStrCombin
Посредством конструктора класса разным членам данных присваиваются значения по умолчанию:
CStrCombin::CStrCombin():m_mode(0),m_places(0),m_pHead(NULL),
m_combNbr(0),m_combTime(0)
{ }
SetGenMode
Позволяет выбрать режим вычислений, используемый алгоритмом. Есть 3 варианта:
1. combWithRep: Если выбран, алгоритм будет вычислять компоновки с повторами
2. combWithoutRep: Если выбран, алгоритм будет вычислять компоновки без повторов
3. combComb: Если выбран, алгоритм будет вычислять комбинации
Код функции имеет вид:
//вызывается первым
void CStrCombin::SetGenMode(int mode)
{
// устанавливает режим вычислений.
if( mode == combWithRep || mode == combWithoutRep || mode == combComb)
m_mode=mode;
else
throw "Недопустимое значение режима!";
}
Эта функция должна вызываться раньше остальных членов-функций.
SetGenStr
Сохраняет последовательность, из которой будут строиться генерируемые последовательности.
Код функции имеет вид:
//вызывается после SetGenMode
void CStrCombin::SetGenStr(char* str)
{
// сохраняет последовательность набора символов
if(!str)
throw "Недопустимый адрес строки!";
if(!strlen(str))
throw "Недопустимое значение строки!";
memset(m_str,0,m_StrSize+1);
strcpy(m_str,str);
}
Эта функция должна вызываться после SetGenMode.
SetGenPlaces
Эта функция устанавливает количество мест. Код имеет вид:
//вызывается после SetGenStr
void CStrCombin::SetGenPlaces(int places)
{
// устанавливает размер генерируемой последовательности в байтах
if( m_mode != combWithRep && m_mode != combWithoutRep &&
m_mode != combComb)
throw "Недопустимое значение режима!";
if ( places<=0 || ( (m_mode==combWithoutRep || m_mode == combComb)
&& strlen(m_str)<places) )
throw "Недопустимое значение мест!";
m_places=places;
}
GenAndSaveCombToFile
Вычисляет и генерирует комбинации или компоновки. Затем сохраняет их в указанный файл. Эта функция использует класс CBuffer.
Код имеет вид:
//вызывается после SetGenPlaces
void CStrCombin::GenAndSaveCombToFile(char* path)
{
// это функция вычислений
m_combTime=GetTickCount();
HANDLE hFile=CreateFile(path,GENERIC_WRITE,0,NULL,
CREATE_ALWAYS,FILE_ATTRIBUTE_NORMAL,NULL);
if(hFile==INVALID_HANDLE_VALUE)
throw "Невозможно создать файл";
// инициализируется максимальный диапазон и начальное значение
CBuffer maxRge(strlen(m_str)-1,m_places);
CBuffer counter(m_places);
for(counter;counter<=maxRge;counter++)
{//00
bool save=true;
for(int i=0;i<counter.m_size;i++)
if(counter.m_buf[i]>=strlen(m_str))
{
save=false;
break;
}
if(m_mode == combWithoutRep || m_mode == combComb)
{
for(int i=0;i<counter.m_size-1;i++)
for(int j=i+1;j<counter.m_size;j++)
if(counter.m_buf[i]==counter.m_buf[j])
{
save=false;
goto _skip;
}
if(m_mode == combComb)
for(int i=0;i<counter.m_size-1;i++)
for(int j=i+1;j<counter.m_size;j++)
if(counter.m_buf[j]<counter.m_buf[i])
{
save=false;
goto _skip;
}
}
_skip:
if(!save) continue;
//добавить значение в связанный список ...
push(counter.m_buf);
m_combNbr++;
}//00
//сохранить значение из связанного списка в файл...
while(m_pHead)
pop(hFile);
CloseHandle(hFile);
m_combTime=GetTickCount()-m_combTime;
}
push
//добавляет значение в верх стека
void CStrCombin::push(unsigned char* str)
{
stack_cell* pTmp=m_pHead;
m_pHead=new stack_cell;
m_pHead->prev=pTmp;
m_pHead->buf=new unsigned char[m_places];
memcpy(m_pHead->buf,str,m_places);
}
pop
//сохраняет и удаляет значение вверху стека
void CStrCombin::pop(HANDLE hFile)
{
if(m_pHead)
{
stack_cell* pTmp=m_pHead->prev;
char* str=new char[m_places+3];
memset(str,0,m_places+3);
for(int i=0;i<m_places;i++)
str[i]=m_str[m_pHead->buf[i]];
strcat(str,"\r\n");
delete []m_pHead->buf;
delete m_pHead;
m_pHead=pTmp;
DWORD dw;
SetFilePointer(hFile,0,0,FILE_END);
WriteFile(hFile,str,strlen(str),&dw,NULL);
}
}
GetCombFoundNbr
"code-string">FONT-WEIGHT: 400">//found combinations number
unsigned long long CStrCombin::GetCombFoundNbr()
{
return m_combNbr;
}[___strong_>
GetCombTime
"code-string">FONT-WEIGHT: 400">// elapsed calculation time
unsigned [___strong_>">FONT-WEIGHT: 400">long long CStrCombin::GetCombTime()
{
return m_combTime;
}[___strong_>
Теперь класс CStrCombin готов к работе. В следующем разделе вы увидите испытание объясненного метода: конкретный пример, использующий CStrCombin.
Пример
Рассмотрим пример для тестирования класса CStrCombin. Код находит все компоновки с повторами для последовательности ABCD и сохраняет результаты в файл.
#include <span class="code-string">"stdafx.h"
</span>
#include <span class="code-keyword"><iostream>
</span>
#include <span class="code-string">"StrCombin.h"
</span>
#include <span class="code-keyword"><windows.h>
</span>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
try
{
// наглядный пример:
//------------------------------------------------------------------
CStrCombin obj;
obj.SetGenMode(CStrCombin::combWithRep);
obj.SetGenStr("ABCD");
obj.SetGenPlaces(4);
obj.GenAndSaveCombToFile("c:\\GenCombs.txt");
//------------------------------------------------------------------
HANDLE hF=CreateFile("c:\\CombInfos.txt",GENERIC_WRITE,0,NULL,
CREATE_ALWAYS,FILE_ATTRIBUTE_NORMAL,NULL);
DWORD dw;
char w[100];
sprintf(w,"%d комбинаций найдено.\r\n%d мс прошло.\r\n",
(unsigned int)obj.GetCombFoundNbr(),
unsigned int)obj.GetCombTime());
SetFilePointer(hF,0,0,FILE_END);
WriteFile(hF,w,strlen(w),&dw,NULL);
CloseHandle(hF);
//-------------------------------------------------------------------
}
catch(char* str)
{
cout<<str<<endl;
}
return 0;
}