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

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

Необязательные параметры

В некоторых случаях удобно создавать функции и генераторы с необязательным параметром:
def gen(n, dummy=0):
    if n == 0:
        yield 'x'
    else:
        for prev in gen(n - 1, dummy + 1):
            yield 'Dummy=' + str(dummy) + ', prev="' + prev + '"'
print(*gen(4), sep='\n')
В этом листке в этих необязательных параметрах можно передавать дополнительные ограничения, на выдаваемые генератором последовательности (например, ограничения на количество единиц, флаг запрета начинать последовательность с единицы и т.д.)

Вообще любой необязательный параметр (а их может быть сколько угодно) имеет вид par_name=default_value. В этом случае, если при вызове этот параметр не передаётся, то используется значение по умолчанию (default_value в нашем примере). Не следует использовать в качестве значения по умолчанию изменяемые объекты (списки, словари, множества и т.п.). В этом случае необходимо использовать значение по умолчанию None:

def func(lst=None)
    if lst is None:
        lst = []
    ...

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

По данному натуральному 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

02: 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

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

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

Ввод Вывод
3
0 0 0
0 0 1
0 1 0
1 0 0
1 0 1

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

По данным натуральным n и k (0≤kn, 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

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

По данным натуральным n и k (0≤kn, 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

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

По данным натуральным n и k (0≤kn, 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

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

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

Ввод Вывод
4 2
0 1 0 1
1 0 0 1
1 0 1 0

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

По данным натуральным n и k (nk) выведите все возрастающие последовательности длины 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

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

По данным натуральным n и k (nk) выведите все убывающие последовательности длины 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

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

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

Ввод Вывод
5
1 1 1 1 1
2 1 1 1
2 2 1
3 1 1
3 2
4 1
5

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

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

Ввод Вывод
5
1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3
5

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

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

Ввод Вывод
8 3
3 3 2
4 2 2
4 3 1
5 2 1
6 1 1

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

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

Ввод Вывод
8 3
1 1 6
1 2 5
1 3 4
2 2 4
2 3 3

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

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

Ввод Вывод
3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

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

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

Ввод Вывод
3
((()))
(()())
(())()
()(())
()()()

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

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

Ввод Вывод
4 2
(()()())
(()())()
(())(())
(())()()
()(()())
()(())()
()()(())
()()()()

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

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

( < ) < [ < ]
Ввод Вывод
2
(())
()()
()[]
([])
[()]
[[]]
[]()
[][]

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

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

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

Ввод Вывод
3 10
[}{)](
[[[]]]
[[{}]]
[[][]]
[[]{}]
[[]][]
[[]]{}
[[]]()
[[]()]
[[()]]
[{[]}]