|
Название задачи: Блиц-тур по комбинаторике . |
 |
Условие
Уважаемые господа! Сегодня вам предлагается для каждого из следующих типов комбинаторных объектов:1) перестановки N-элементного множества (лексикографический порядок);
2) K-элементные подмножества N-элементного множества (лексикографический порядок);
3) разбиения N-элементного множества на K непустых подмножеств (лексикографический, т.е. алфавитный, порядок);
4) разбиения числа N на слагаемые;
5) правильные скобочные последовательности из 2N скобок;
6) двоичные деревья с N вершинами;
7) цепочки из нулей и единиц длины N без двух единиц подряд;
8) перестановки N-элементного множества (порядок, в котором соседние перестановки отличаются транспозицией соседних элементов);
9) K-элементные подмножества N-элементного множества (порядок, в котором соседние подмножества отличаются двумя элементами);
10) все подмножества N-элементного множества (порядок, в котором соседние подмножества отличаются добавлением или удалением одного элемента);
11) подвешенные деревья с N вершинами;
решить следующие две подзадачи:
найти общее количество объектов и породить M объектов, начиная с L-го;
по заданным объектам получить их номера.
В качестве N-элементного множества везде подразумевается множество {1, ..., N}. Там, где порядок порождения комбинаторных объектов не указан, Вы можете выбрать его по своему усмотрению. Нумерация объектов начинается с нуля.
Таким образом, Вам предстоит написать 11 программ. Задача
засчитывается, если Ваша программа прошла все тесты, в противном случае
Вам начисляются штрафные баллы за неверный подход (20% от стоимости
задачи), и Вы имеете возможность исправить решение.
В зависимости от того, какую из подзадач требуется решить, входной и
выходной файлы имеют один из следующих двух форматов (тем самым, Ваша
программа должна сама определять номер решаемой подзадачи).
Входные данные для подзадачи 1
N K L M
Выходные данные для подзадачи 1
<Число объектов>
<Объект номер L>
...
<Объект номер L+M-1>
Каждый объект должен выводиться с новой строки. Формат вывода объектов
остается на Ваше усмотрение с условием, что он должен быть читабельным.
Входные данные для подзадачи 2
N K
<Объект 1>
...
<Объект M>
Формат записи объектов будет соответствовать выходному формату,
используемому Вашей программой при решении подзадачи 1.
Выходные данные для подзадачи 2
<Номер объекта 1>
...
<Номер объекта M>
Каждый номер должен быть выведен с новой строки.
Технические ограничения
Если в данной задаче число K не используется, то вместо него будет указан
нуль. Числа N и K во всех задачах не превосходят 100, число L не превышает
2·109
, число M – 10 000. Номера объектов в подзадаче 2 не будут превышать
2.1·109. Все входные данные корректны.
Решение
Для каждого упомянутого в условии типа комбинаторных объектов необходимо научиться решать следующие задачи (считаем, что порядок объектов выбран):1. Определить количество объектов.
2. Найти объект по номеру.
3. Найти номер по объекту.
4. Получить по объекту следующий.
Хотя последний пункт и сводится к двум предыдущим, существенно эффективнее будет процедура, решающая подзадачу 1 с помощью пункта 4.
Рассмотрим принципы решения сформулированных задач на примере перестановок, разбиений на слагаемые и цепочек из нулей и единиц без двух единиц подряд (чтобы не писать каждый раз столько слов, назовем их просто хорошими).
Перестановки (лексикографический порядок)
Количество перестановок из N элементов равно N! – это известная комбинаторная формула. Порождение всех перестановок из N элементов будем проводить «по индукции». Предположим, что мы умеем порождать все перестановки из N-1 числа. Тогда сначала сгенерируем все перестановки чисел 2, ..., N, приписывая к ним слева единицу. Затем сгенерируем все перестановки чисел 1, 3, ..., N, приписывая к ним слева двойку, и т.д. Последним шагом будет порождение всех перестановок чисел 1, ..., N-1 с приписыванием к ним слева числа N.
Можно, конечно, запрограммировать этот метод напрямую. Но давайте проанализируем его более внимательно. Из описанной процедуры вытекает, что каждая следующая перестановка получается из предыдущей таким образом. В «предыдущей» перестановке x1, ..., xn справа ищется наибольшая убывающая подпоследовательность чисел xi > ... > xn (если рассматривать позиции, начиная с i-ой, то это последняя перестановка чисел xi, ..., xn). Если i = 1, то все перестановки были сгенерированы. Иначе среди чисел x i , ..., x n выбирается наименьшее xj, большее xi-1, и ставится на позицию i-1, а все оставшиеся числа (и xi-1 в том числе) выписываются в возрастающем порядке.
Таким образом, мы научились эффективно генерировать все перестановки, а
заодно и решили задачу получения по перестановке следующей. Пример работы
нашего алгоритма для N = 4 приведен на рисунке.
Алгоритм вычисления по перестановке ее номера также несложно получить,
анализируя описанный метод порождения. Будем, опять же, действовать «по
индукции». Предположим, что мы уже умеем вычислять номер по перестановке
из N-1 числа, и нам задана произвольная перестановка из N чисел. Пусть x – ее
первое число. Тогда все перестановки с первыми числами от 1 до
x-1 находятся перед нашей. Их количество num равно
(x-1)·(N-1)!. Осталось узнать номер перестановки из N-1 числа, получающейся из нашей выбрасыванием числа
x, и прибавить этот номер к num.
Алгоритм получения перестановки по ее номеру реализуется аналогично:
сначала определяем первую цифру перестановки, деля номер на (N-1)! и
прибавляя 1, затем вторую, деля остаток от предыдущего деления на
(N-2)!, и т.д.
Перестановки (отличающиеся транспозицией соседних элементов)
Пусть мы умеем генерировать в требуемом порядке все перестановки,
состоящие из N-1 числа 2, ..., N. Сгенерируем первую такую перестановку.
Будем последовательно вставлять единицу на первое, второе, ..., N-ое место.
Затем, оставляя единицу на том же месте, сгенерируем следующую
перестановку чисел 2, ..., N, после чего «тащим» единицу влево и т.д. В
результате получим все перестановки чисел 1, ..., N в требуемом порядке (см.
рис.).
Разберем этот метод подробнее. В процессе генерирования перестановок
над каждым числом будет записана стрелка, которая указывает, куда мы это
число в данный момент тащим (влево или вправо). В начальный момент
порождается перестановка 1, 2, ..., N, а все стрелки указывают вправо. Затем мы
берем самый младший элемент нашего множества – единицу – и тащим его по
направлению его стрелки (вправо) до тех пор, пока он не «упрется», т.е. не
достигнет последней возможной позиции. После этого мы меняем направление
стрелки над единицей, берем следующий по старшинству элемент – двойку –
и сдвигаем его на одну позицию по стрелке. Далее опять тащим единицу, но уже
в противоположном направлении, и т.д. То есть для получения следующей перестановки на очередном шаге мы
берем единицу и пробуем тащить ее по стрелке. Если она уперлась, то меняем ее
стрелку и пробуем тащить двойку. Если и она уперлась, меняем ее стрелку, и
пробуем сдвинуть тройку. И т.д. Если уперлись все, то перестановок больше не
будет.
Рассмотрим теперь, как по номеру K получить K-ую перестановку. Соответствующий алгоритм легко следует из метода генерирования. Ясно, что если перестановка чисел 2, ..., N имеет четный номер, то единица тащится вправо, иначе – влево. Следовательно, мы должны взять перестановку чисел 2, ..., N с номером [K / N] и вставить в нее единицу на позицию (K mod N) + 1. При этом позиция отсчитывается справа или слева в зависимости от четности числа [K / N].
Для вычисления по перестановке ее номера обозначим через L номер
перестановки чисел 2, ..., N, полученной из исходной удалением единицы.
Определив четность L, мы узнаем, в каком направлении единица тащится. Тем
самым, нам станет известно, справа или слева отсчитывать ее позицию. Пусть
номер этой позиции M. Тогда искомый номер перестановки будет равен
L·N
+
M
-
1.
Упражнения
1. Сформулируйте признак, по которому определяется, «уперлось» число или
нет.
2. Решите те же задачи для K-элементных подмножеств N-элементного
множества.
Разбиения на слагаемые
Необходимо заметить, что разбиения, отличающиеся только порядком
слагаемых, мы считаем совпадающими. Назовем (N, K)-разбиениями все те
разбиения числа N, для которых каждое из слагаемых не превосходит K. Пусть
A(N, K) – количество таких разбиений. Числа A(N, K) будем вычислять
методом динамического программирования. Для вывода рекуррентной формулы
разделим все (N, K)-разбиения на два класса. В первый попадут разбиения, в
которых есть слагаемые, равные K, а во второй – все остальные. Ясно, что
количество разбиений во втором классе равно A(N, K-1). Найдем количество
разбиений в первом. Заметим, что если из каждого разбиения этого класса
выбросить одно число K (а их может быть несколько), то получим все (N-K, K)-разбиения. Следовательно, верна следующая формула:
A(N, K) = A(N, K-1)
+
A(N-K, K).
Перейдем к задаче генерирования (N, K)-разбиений. Каждое разбиение единственным образом записывается в виде последовательности чисел, расположенных в порядке невозрастания. Будем порождать (N, K)-разбиения в антилексикографическом порядке, т.е. порядке, обратном алфавитному (рисунок демонстрирует этот порядок для (7, 5)-разбиений). Для этого, согласно предыдущим рассуждениям, необходимо сгенерировать сначала все (N-K, K)-разбиения, приписывая к каждому из них слева число K, а затем сгенерировать все (N, K-1)-разбиения.
Как получить по (N, K)-разбиению следующее? Каждое разбиение выглядит таким образом: сначала идут числа, большие единицы, а затем – только единицы. Пусть L – количество единиц в разбиении. Найдем первое число справа, большее единицы, и обозначим его через x. Тогда следующее разбиение будет таким: все числа до x останутся теми же самыми, вместо x будет стоять x-1, а дальше – первое разбиение числа L+1 на слагаемые, не превосходящие x-1.
Рассмотрим задачу вычисления по (N, K)-разбиению его номера. Пусть x – первое число заданного разбиения. Тогда все разбиения с первым числом от x+1 до min(K, N) предшествуют нашему. Их общее количество num равно (докажите это!) A(N - (x+1), x+1) + A(N - (x+2), x+2) + ... + A(N - min(K, N), min(K, N)).
Пусть P – номер того разбиения числа N-x на слагаемые, не превосходящие x, которое получается из исходного вычеркиванием первого числа. Тогда номером исходного разбиения будет num+P.
Аналогично осуществляется построение разбиения по номеру: определяем
сначала первое число разбиения, затем второе и т.д.
Упражнения
1. Решите те же задачи для правильных скобочных последовательностей. Для
этого воспользуйтесь числами B(N, K), равными количеству начал
правильных скобочных последовательностей длины N с балансом K
(балансом называется количество открывающих скобок минус количество
закрывающих, см. также задачу 1.2).
2. Попробуйте вывести явную формулу для числа правильных скобочных
последовательностей.
3. Найдите взаимно однозначное соответствие между правильными
скобочными последовательностями и подвешенными деревьями. Это
соответствие сведет одиннадцатый тип комбинаторных объектов блиц-тура
к пятому.
4. Найдите взаимно однозначное соответствие между подвешенными и
двоичными деревьями. Это соответствие сведет шестой тип комбинаторных
объектов блиц-тура к пятому.
Цепочки из нулей и единиц длины N без двух единиц подряд
Количество хороших цепочек длины N равно числу Фибоначчи с номером N+1
(см. задачу 1.1). Рассмотрим задачу перечисления этих цепочек в
лексикографическом порядке. Пусть мы умеем генерировать хорошие цепочки
длины N-1 и длины N-2. Тогда для порождения хороших цепочек длины N
сначала порождаем все хорошие цепочки длины N-1 и приписываем к каждой
из них слева 0, затем порождаем все хорошие цепочки длины N-2 и
приписываем к каждой из них слева 10.
Из приведенного метода вытекает следующий способ получения следующей
в лексикографическом порядке хорошей цепочки. В имеющейся цепочке
выделяем справа максимальную подцепочку вида 1010...1 или вида
1010...10, ставим перед ней единицу, а все числа правее этой единицы
заменяем на нули.
Упражнения
1. Придумайте алгоритмы получения номера по хорошей цепочке и хорошей
цепочки по номеру.
2. Решите все рассмотренные задачи, если хорошие цепочки нужно
генерировать в таком порядке, чтобы каждая следующая отличалась от
предыдущей ровно в одной цифре.
