Порождение комбинаторных объектов
Решения задач на порождение комбинаторных объектов в своей основе имеют одну и ту же схему, которая предполагает ответ на следующие вопросы:
- Каков порядок порождения комбинаций? (иногда это оговорено в условии)
- Как получить первую комбинацию?
- Как, имея заданную комбинацию, получить следующую?
- Как проверить, является ли текущая комбинация последней?
Примечание: вопросы 2 и 4, как правило, решаются крайне легко
Сама же процедура порождения всех комбинаций обычно имеет следующий вид:
процедура получитьВсеКомбинации
| получитьПервуюКомбинацию
| вывести Комбинацию
| пока не текущаяКомбинацияПоследняя выполнять
| | получитьСледующуюКомбинацию
| | вывести Комбинацию
| конецЦикла
|конецПроцедуры
В задачах этого листка:
- Использование вышеописанной процедуры и, таким образом, всех ее подпрограмм обязательно.
- Рекурсия запрещена.
- Для хранения комбинаций используется глобальный массив и соответствующие константы; данные с клавиатуры не вводятся.
- Время выполнения процедуры получитьСледующуюКомбинацию, по умолчанию не более Cn.
07_01a (0)
Напечатать все последовательности длины
n из чисел
0.. k-1 в лексикографическом порядке
07_01b (1)
Напечатать все последовательности длины
n из чисел
0.. k-1 в
обратном лексикографическом порядке
07_01c (2)
Напечатать все последовательности длины
n у которых
i-ый член не превосходит
i.
07_01d (4)
Напечатать все последовательности длины
n из чисел
0.. k-1 так, чтобы соседние последовательности отличались бы только в одной позиции и только на единицу.
07_02 (3)
Напечатать все подмножества множества
1 .. k.
07_03a (4)
Напечатать все перестановки чисел
1 .. n, то есть последовательности длины
n, в которые каждое из этих чисел входит по одному разу.
07_03x (3)
Написать функцию
int nPermut(int *perm, int n), которая по заданному
n и перестановке первых
n чисел
perm возвращает ее номер при лексикографическом перечислении.
пример 1: при
n=5 и
perm[] = {1, 2, 3, 4, 5} возвращается 1.
пример 2: при
n=4 и
perm[] = {1, 2, 4, 3} возвращается 2.
пример 3: при
n=3 и
perm[] = {3, 2, 1} возвращается 6.
07_03y (3)
Написать функцию
int *permutByNum(int k, int n), обратную к функции из предыдущей задачи по заданному
n и
номеру
k перестановки первых
n чисел при лексикографическом перечислении возвращает указатель на массив с этой перестановкой.
пример 1: при
n=5 и
k= 1
permutByNum возвращается указатель на {1, 2, 3, 4, 5}.
пример 2: при
n=4 и
k= 2
permutByNum возвращается указатель на {1, 2, 4, 3}.
пример 3: при
n=3 и
k= 6
permutByNum возвращается указатель на {3, 2, 1}.
07_03b (5)
То же, что и в
07_03a но еще так, чтобы соседние последовательности получались бы друг из друга обменом лишь двух элементов.
07_04 (2)
Перечислить все возрастающие последовательности длины
k из чисел
1 .. n в лексикографическом порядке.
пример: при
n=5,
k=2 получаем 12 13 14 15 23 24 25 34 35 45)
07_05a (4)
Перечислить все разбиения целого положительного числа
n на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно). разбиения представляются как невозрастающие последовательности, порядок перечисления – лексикографический.
пример: для
n = 4, разбиения 1+1+1+1, 2+1+1, 2+2, 3+1, 4.)
07_05b (4)
Представляя по-прежнему разбиения как невозрастающие последовательности, переписать их в порядке, обратном лексикографическому.
пример: для
n = 4, должно быть 4, 3+1, 2+2, 2+1+1, 1+1+1+1).
07_05c (4)
Представляя разбиения как неубывающие последовательности, перечислить их в лексикографическом порядке.
пример: для
n = 4: 1+1+1+1, 1+1+2, 1+3, 2+2, 4;
07_06 (3)
Перечислить все вложения (т. е. функции, переводящие разные элементы в разные) множества {1..
k} в {1..
n}, где
k не превышает
n.
07_07 (4)
Перечислить все последовательности нулей и единиц длины 2
n, содержащие
n нулей и
n единиц, такие, что в любом их начальном отрезке число единиц не превосходит числа нулей.
07_08 (4)
На окружности задано 2
n пронумерованных точек Перечислить все способы провести
nнепересекающихся хорд, с вершинами в этих точках.
07_09 (4)
Перечислить все способы разрезать выпуклый
n–угольник на треугольники, проведя
n–3 его диагонали.
07_10 (5)
Перечислить все способы расстановки скобок в произведении
n сомножителей. Порядок сомножителей не меняется, скобки полностью определяют порядок действий.
пример: для
n = 4 существует 5 расстановок:
- ((a...b)..c)..d
- .(a..(b...c)).d
- .(a...b).(c...d)
- ..a.((b...c)..d)
- ..a..(b..(c...d))