Рекурсивный перебор комбинаторных объектов

Во всех задачах этого листка необходимо сгенерировать все числовые последовательности, удовлетворяющие условию, в лексикографическом или обратном лексикографическом порядке. Ввод-вывод стандартный. Каждая последовательность должен выводиться в отдельной строке, вывод должен завершаться символом новой строки. Числа, входящие в последовательность, должны быть разделены одним пробелом (если в условии не оговорено иное). В начале и конце каждой строки допускаются пробелы.

Все задачи должны решаться при помощи рекурсивной функции.

Упражнения

A: Двоичные последовательности

По данному натуральному n≤10 выведите все двоичные последовательности длины n в лексикографическом порядке.

3

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

B: k-ичные последовательности

По данным натуральным n и k (2≤k≤10) выведите все последовательности длины n, составленные из символов 0..k-1. в лексикографическом порядке.

Пример

2 3

0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

C: Двоичные последовательности без двух единиц подряд

По данному натуральному n≤20 выведите все двоичные последовательности длины n, не содержащие двух единиц подряд, в лексикографическом порядке.

3

0 0 0
0 0 1
0 1 0
1 0 0
1 0 1

D: Двоичные последовательности длины n содержащие не более k единиц

По данным натуральным n и k (0≤k≤n, n≥1) выведите все двоичные последовательности длины n, содержащие не более k единиц в лексикографическом порядке.

4 2

0 0 0 0
0 0 0 1
0 0 1 0 
0 0 1 1
0 1 0 0 
0 1 0 1
0 1 1 0
1 0 0 0
1 0 0 1
1 0 1 0
1 1 0 0

E: Двоичные последовательности длины n содержащие k единиц

По данным натуральным n и k (0≤k≤n, n≥1) выведите все двоичные последовательности длины n, содержащие ровно k единиц в лексикографическом порядке.

4 2

0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0

F: Двоичные последовательности длины n содержащие не более k единиц без двух единиц подряд

По данным натуральным n и k (0≤k≤n, n≥1) выведите все двоичные строки длины n содержащие не более k единиц и не содержащие двух единиц подряд в лексикографическом порядке.

4 2

0 0 0 0
0 0 0 1
0 0 1 0
0 1 0 0 
0 1 0 1
1 0 0 0
1 0 0 1
1 0 1 0

G: Двоичные последовательности длины n содержащие k единиц без двух единиц подряд

По данным натуральным n и k (0≤k≤n, n≥1) выведите все двоичные строки длины n содержащие k единиц и не содержащие двух единиц подряд в лексикографическом порядке.

4 2

0 1 0 1
1 0 0 1
1 0 1 0

H: Возрастающие последовательности

По данным натуральным n и k (n≤k) выведите все возрастающие последовательности длины n, состоящие из чисел 1..k.

3 5

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

I: Убывающие последовательности

По данным натуральным n и k (n≤k) выведите все убывающие последовательности длины n, состоящие из чисел 1..k в обратном лексикографическом порядке.

3 5

5 4 3
5 4 2
5 4 1
5 3 2
5 3 1
5 2 1
4 3 2
4 3 1
4 2 1
3 2 1

J: Разбиение на невозрастающие слагаемые

Дано натуральное число n. Выведите всевозможные его разбиения на слагаемые, упорядоченные в порядке невозрастания. Сами разбиения необходимо выводить в лексикографическом порядке.

5

1 1 1 1 1
2 1 1 1
2 2 1
3 1 1
3 2
4 1
5

K: Разбиение на неубывающие слагаемые

Дано натуральное число n. Выведите всевозможные его разбиения на слагаемые, упорядоченные в порядке неубывания. Сами разбиения необходимо выводить в лексикографическом порядке.

5

1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3
5

L: Разбиение на k невозрастающих слагаемых

Даны натуральные числа n и k (1≤k≤n). Выведите всевозможные разбиения числа n на kслагаемых, упорядоченных в порядке невозрастания. Сами разбиения необходимо выводить в лексикографическом порядке.

8 3

3 3 2
4 2 2
4 3 1
5 2 1
6 1 1

M: Разбиение на k неубывающих слагаемых

Даны натуральные числа n и k (1≤k≤n). Выведите всевозможные разбиения числа n на kслагаемых, упорядоченных в порядке неубывания. Сами разбиения необходимо выводить в лексикографическом порядке.

8 3

1 1 6
1 2 5
1 3 4
2 2 4
2 3 3

N: Перестановки

Дано натуральное число n. Выведите всевозможные перестановки чисел от 1 до n в лексикографическом порядке.

3

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

O: Правильные скобочные последовательности

Дано натуральное числo n. Выведите все правильные скобочные последовательности, состоящие из n открывающихся круглых скобок и n закрывающихся скобок в лексикографическом порядке.

3

((()))
(()())
(())()
()(())
()()()

P: Правильные скобочные последовательности вложенности не более k

Даны натуральные числа n и k. Выведите все правильные скобочные последовательности, состоящие из n открывающихся круглых скобок и n закрывающихся скобок таки, что максимальная вложенность не превосходит k в лексикографическом порядке.

4 2

(()()())
(()())()
(())(())
(())()()
()(()())
()(())()
()()(())
()()()()

Q: Правильные скобочные последовательности - 2

Дано натуральное числo n. Выведите все правильные скобочные последовательности, состоящие из n открывающихся скобок и n закрывающихся скобок в лексикографическом порядке. Используются круглые и квадратные скобки, их порядок следующий:

2

(())
()()
()[]
([])
[()]
[[]]
[]()
[][]

R: Правильные скобочные последовательности - 3

Дано натуральное числo n. Выведите k первых в лексикографическом порядке правильных скобочных последовательности, состоящих из n открывающихся скобок и n закрывающихся скобок в лексикографическом порядке. Используются круглые, квадратные и фигурные скобки. Лексикографичесчкий порядок для скобок задается в тестовых данных. Программа получает на вход число n - количество открывающихся скобочек в исходной последовательности, количество правильных скобочных последовательностей k, которые необходимо вывести (nk≤10⁶). Затем идет строка из 6 символов, являющаяся некоторой перестановкой строки "()[]{}", задающая лексикографический порядок.

Гарантируется, что существует k правильных последовательностей указанной длины.

3 10
[}{)](

[[[]]]
[[{}]]
[[][]]
[[]{}]
[[]][]
[[]]{}
[[]]()
[[]()]
[[()]]
[{[]}]

S: Расстановки ферзей

Известно, что на шахматной доске размером 8×8 можно расставить 8 ферзей не бьющих друг друга, причем сделать это можно 92 способами.

Дано натуральное n≤12. Определите сколькими способами на доске n×n можно расставить n мирных ферзей.

8

92

T: Расстановки ферзей - 2

Решите предыдущую задачу, если расстановки ферзей, которые можно получить друг из друга поворотами и отражениями доски считать за одно.

8

12