Решения задач на порождение комбинаторных объектов в своей основе имеют одну и ту же схему, которая предполагает ответ на следующие вопросы:
Примечание: вопросы 2 и 4, как правило, решаются крайне легко
Сама же процедура порождения всех комбинаций обычно имеет следующий вид:
процедура получитьВсеКомбинации
| получитьПервуюКомбинацию
| вывести Комбинацию
| пока не текущаяКомбинацияПоследняя выполнять
| | получитьСледующуюКомбинацию
| | вывести Комбинацию
| конецЦикла
|конецПроцедуры
В задачах этого листка:
07_01a (начальная)
Напечатать все последовательности длины n из чисел 0.. k-1 в лексикографическом порядке
07_01b (легкая)
Напечатать все последовательности длины n из чисел 0.. k-1 в обратном лексикографическом порядке
07_01c (легкая)
Напечатать все последовательности длины n у которых i-ый член не превосходит i.
07_01d (трудная)
Напечатать все последовательности длины n из чисел 0.. k-1 так, чтобы соседние последовательности (а также первая и последняя) отличались бы только в одной позиции и только на единицу.
07_02 (средняя)
Напечатать все подмножества множества 1 .. k.
07_03a (3)
Напечатать все перестановки чисел 1 .. n, то есть последовательности длины n, в которые каждое из этих чисел входит по одному разу.
07_03b (3)
Написать функцию int nPermut(int *perm, int n), которая по заданному n и перестановке первых n чисел perm возвращает ее номер при лексикографическом перечислении.
пример 1: при n=5 и perm[] = {1, 2, 3, 4, 5} nPermut возвращает 1.
пример 2: при n=4 и perm[] = {1, 2, 4, 3} nPermut возвращает 2.
пример 3: при n=3 и perm[] = {3, 2, 1} nPermut возвращает 6.
07_03c (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_03d (5)
То же, что и в 07_03a но еще так, чтобы соседние последовательности получались бы друг из друга обменом лишь двух элементов.
07_04 (средняя)
Перечислить все возрастающие последовательности длины k из чисел 1 .. n в лексикографическом порядке.
5.
6. Перечислить все вложения (т. е. функции, переводящие разные элементы в разные) множества {1..k} в {1..n}, где k не превышает n.
7. Перечислить все последовательности нулей и единиц длины 2n, содержащие n нулей и n единиц, такие, что в любом их начальном отрезке число единиц не превосходит числа нулей.
8. Перечислить все способы расстановки скобок в произведении n сомножителей. Порядок сомножителей не меняется, скобки полностью определяют порядок действий.
9. На окружности задано 2n пронумерованных точек Перечислить все способы провести nнепересекающихся хорд, с вершинами в этих точках.
10. Перечислить все способы разрезать выпуклый n–угольник на треугольники, проведя n–3 его диагонали.