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

ОГЛАВЛЕНИЕ

Статья о быстрой генерации всевозможных перестановок и комбинаций новым и простым образом

•    Скачать демонстрационный проект- 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