Комбинаторные алгоритмы. Индикативные множества презентация

Полное построение алгоритма для решения комбинаторной задачи

состоит в переборе элементов x множества X.
Задача: Сколькими способами можно выбрать M из N различных предметов?
Ответ - сочетания

Формула Ньютона
Σ СiN = 2N

Ежегодно в Канны на кинофестиваль едет некоторое количество из них. Сформировать и вывести последовательность командировок (все возможные варианты), если каждая следующая делегация содержит в себе одного нового члена СК.
(Вариант формулировки: отправка делегации болельщиков на Олимпиаду)

одну командировку.
Надо:
Вывести последовательность ежегодных командировок.
Дополнительная информация:
Каждая новая командировка содержит одного нового члена делегации.

всех их целыми числами (1, 2, 3, 4, 5).
Таким образом, необходимо выписать последовательность сочетания трех чисел из пяти.
Сколько сочетаний по 3 из 5?
Сkn=n!/(k!⋅(n-k)!)

5! / (3!2!) = 1*2*3*4*5 / (1*2*3*1*2) =10
Как выписать сочетания?
Обозначим состояние поездки одного кинематографиста: 1 - едет; 0 - не едет (бинарная арифметика).
Тогда состав делегации может быть обозначен вектором с пятью компонентами.
Например, вектор (1, 0, 0, 1, 1) означает, что 1, 4, 5 кинематографисты включены в делегацию, а 2 и 3 нет.

количество которых 2n. Для нашего примера 25=32.
Определение:
Индикативное множество - множество, состоящее только из единиц и нулей. (Индикатор – место, на котором они стоят.)
Составим индикативное множество из n элементов

K - количество членов делегации.
Выходные данные:
Составы делегаций
Алгоритм:
Ввести n и k.
Выписать числа в двоичном коде от 0 до 2N
Выбрать числа, у которых ровно k единиц.
Для каждого такого числа выписать номера разрядов, в которых стоит единица, и вывести эти номера разрядов (список сочетаний).

числа с k единицами (kДля каждого выбранного i-того двоичного числа можно указать номер разряда, где стоит единица, а значит, выписать сочетание Сni
Алгоритм конечен, так как просматривается конечное количество двоичных чисел.

эта часть алгоритма потребует О(2n) шагов. В каждом числе ищем количество единиц за О(n) шагов (либо сумм, либо сравнений).
Для каждой Сkn выписываем k разрядов за О(Сkn) = О(n!/(k!(n-k)!)⋅k) шагов.
Итого fA(n)=O(2n⋅n+ n!/(k!(n-k)!)⋅k) = O(n⋅[2n+(n-1)!/((k-1)! ⋅(n-k)!)]
(применить формулу Стирлинга для вычисления факториала)

1 до n. Написать программу, которая выводит все возможные составы делегаций из k членов согласно их членским билетам (все возможные сочетания из n по k - Сkn )
Задание 2: Пусть имеется алфавит, состоящий из n символов. Описать полное построение алгортима, который для заданной строки, составленной из символов данного алфавита, вычисляет частоту появления каждого символа.