Комбинаторика
Рассматриваем линейное представление структур
Пример: Для двоичной кучи - массив содержащий элементы кучи
Цели:
- Подсчёт и перечисление комбинаторных объектов
- Нумерация комбинаторных объектов
Вектора фиксированной длины
Над алфавитом
Лексикографический порядок
Пусть
- На
введено отношение порядка - Линейно
Перенесём порядок с
на лексикографический
Пример: 2
векторы без двух " " подряд
Будем бить на непересекающиеся мн-ва
Перестановки (Permutation)
Размещения (Arrangement)
Сочетание (Binomial coefficients)
Выбираем
Канонизация (избавление от
Код Грея
Способ перечисления комбинаторных объектов, чтобы они как можно меньше локально менялись
Пример: Для векторов длины
Теорема
(Круги эйлера)