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