%%(wacko wrapper=text wrapper_align=center) ==== Порождение комбинаторных объектов == %%
Решения задач на порождение комбинаторных объектов в своей основе имеют одну и ту же схему, которая предполагает ответ на следующие вопросы:
1. Каков порядок порождения комбинаций? (иногда это оговорено в условии)
1. Как получить первую комбинацию?
1. Как, имея заданную комбинацию, получить следующую?
1. Как проверить, является ли текущая комбинация последней?
__**Примечание:**__ вопросы 2 и 4, как правило, решаются крайне легко
Сама же процедура порождения всех комбинаций обычно имеет следующий вид:
##**процедура** //получитьВсеКомбинации//##
##| //получитьПервуюКомбинацию//##
##| //вывести Комбинацию//##
##| **пока не** //текущаяКомбинацияПоследняя// **выполнять**##
##| | //получитьСледующуюКомбинацию//##
##| | //вывести Комбинацию//##
##| **конецЦикла**##
##|**конецПроцедуры**##
----
**В задачах этого листка:**
* **Использование вышеописанной процедуры и, таким образом, всех ее подпрограмм !!обязательно!!.**
* **Рекурсия !!запрещена!!.**
* **Для хранения комбинаций используется !!глобальный массив!! и соответствующие константы; данные с клавиатуры !!не вводятся!!.**
* **Время выполнения процедуры** ##//получитьСледующуюКомбинацию//##, **по умолчанию !!не более!! //C""""vvnvv""""//.**
%%(wacko wrapper=text wrapper_align=center) ===== Задачи == %%
**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 расстановок:
1. **##((a...b)..c)..d ##**
1. **##.(a..(b...c)).d ##**
1. **##.(a...b).(c...d) ##**
1. **##..a.((b...c)..d) ##**
1. **##..a..(b..(c...d))##**