[an error occurred while processing the directive]

Занятие 17. Комбинаторика - 3. Генерация объекта по номеру и номера по объекту.

Комбинаторика изучает множества однотипных объектов. Объекты в таком множестве можно упорядочить по некоторому признаку и затем занумеровать. Возникает задача определения объекта по его номеру и номера по объекту. Рассмотрим способ решения этой задачи на примере перестановок фиксированной длины N.

В качестве способа упорядочивания возьмем лексикографический (пример лексикографического порядка перестановок длины 3: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)). Сначала научимся определять перестановку по номеру. Для этого научимся отвечать на вопрос: "Сколько существует объектов с заданным началом?" Для перестановок ответ прост: (N-k)!, где k - длина префикса. Будем перебирать все префиксы длины 1 в лексикографическом порядке. Как только сумма количества перестановок с такими префиксами станет не меньше номера, начинаем перебирать все префиксы длины два, полученные продолжением последнего префикса длины один, и так далее. Обратная задача решается аналогично: перебираем все префиксы длины один, меньшие соответствующего префикса нашей перестановки, затем длины два, полученные продолжением префикса длины один нашей перестановки и т.д. Сумма по всем перебранным префиксам будет на 1 меньше номера перестановки.

Прочие задачи генерации номера по объекту и объекта по номеру решаются аналогично: мы последовательно строим объект, перебирая все возможные начала. Самой сложной частью, как правило, являлется определение количества объектов с заданным префиксом. Если явной формулы не существует, приходится прибегать к динамическому программированию.

Задача 17-1. По номеру!
Задача 17-2. По размещению!
Задача 17-3. Гладкие числа.
Задача 17-4. Следующая...
[an error occurred while processing the directive]