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

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

Пример комбинаторной задачи:
построение сочетаний с помощью
индикативных множеств.
Полное построение алгоритма
для решения комбинаторной
задачи
1

2. Комбинаторные алгоритмы. Сочетания (выборки)

• Задачу имеет смысл называть
комбинаторной, если ее решение состоит в
переборе элементов x множества X.
• Задача: Сколькими способами можно выбрать
M из N различных предметов?
• Ответ - сочетания
Формула Ньютона
СiN = 2N
2

3. Комбинаторные алгоритмы. Сочетания

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

4. Постановка задачи.

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

5. Построение модели

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

6. Организация сочетаний с помощью индикативных множеств.

• C35 = 5! / (3! (5-3)!) = 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 нет.
6

7. Организация сочетаний с помощью индикативных множеств

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

8. Организация сочетаний с помощью индикативных множеств

8

9. Построение алгоритма

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

10. Проверка правильности алгоритма

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

11. Анализ алгоритма и его сложности

• Размерность задачи n.
• Количество двоичных чисел 2n,
• Сл-но, эта часть алгоритма потребует О(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)!)]
11
• (применить формулу Стирлинга для вычисления факториала)

12.

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