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

ОГЛАВЛЕНИЕ

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

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

Читайте также:
  • Манипулирование цветами в .NET – часть первая
    • Скачать демонстрационный проект (.NET 1.1) - 58.8 Кб• Скачать исходники C# (.NET 1.1) - 110.0 Кб• Скачать исходники C# (.NET 2.0) - 111.2 Кб• Скачать исходники VB (.NET 2.0) - 115.7 Кб Введение Почему статья о "цветах"? На самом деле, в .NET, можно использовать только два формата цвета: цвет...
  • Назад к основам – обобщенные структуры данных и алгоритмы в .NET 2.0
    •    Скачать исходники - 265.8 Кб (с тестами NUnit)•    Скачать двоичные файлы - 40.5 Кб•    Домашняя страница проекта NGenerics (CodePlex)Статья не дает все подробности и полные описания внутреннего устройства этих коллекций и алгоритмов - наоборот, она дает ссылки на имеющиеся в интернете ресурс...
  • Определение цен барьерных опционов с помощью сеток. Часть первая – постоянные барьеры
    •    Скачать демонстрационный проект - 5.26 Кб•    Скачать исходники - 12.2 Кб Введение Стоит отметить, что представленный метод можно расширить до вмещения опционов с несколькими постоянными барьерами. После изучения простого примера перейдем к более сложным опционам с изменяющимися во времени ...
  • FuzzyAdvisor – простая экспертная система с нечеткой логикой на F#
    •    Скачать исходники - 108 Кб Введение Более 15 лет назад разрабатывали проект (Brulé и др., 1995), требовавший экспертную систему, выбирающую подходящий вариант исходя из некоторых основных параметров. Были опробованы несколько подходов, в том числе использование исчисления предикатов (...
  • Нейронные сети на C#
    •    Скачать исходники - 251 Кб•    Скачать демонстрационный проект - 181 Кб Введение История нейронных сетей начинается в 1950-х гг., когда была представлена архитектура простейших нейронных сетей. После начальной работы в области идея нейронных сетей стала весьма популярной. Но затем область...