Генерация перестановок и комбинаций в буфере произвольного размера - Основы алгоритма
ОГЛАВЛЕНИЕ
Основы алгоритма
Исходная точка – набор символов, заданный пользователем. Кроме того, пользователь задает желаемое количество мест, которое займут комбинации/компоновки. Алгоритм умеет генерировать компоновки с/без повторов и комбинации. Первый шаг процесса одинаков для 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 "Переполнение буфера!"; //генерировать исключение при появлении ошибки
}