Генерация перестановок и комбинаций в буфере произвольного размера - Функции сравнения

ОГЛАВЛЕНИЕ

Функции сравнения

Сравнения между объектами 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;
}