Генерация перестановок и комбинаций в буфере произвольного размера - Функции сравнения
ОГЛАВЛЕНИЕ
Функции сравнения
Сравнения между объектами 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;
}