Во всех задачах этого листка необходимо сгенерировать все числовые последовательности, удовлетворяющие условию,
в лексикографическом порядке.
Ввод-вывод стандартный.
Каждая последовательность должна выводиться в отдельной строке, вывод должен завершаться символом новой строки.
Числа, входящие в последовательность, должны быть разделены одним пробелом (если в условии не оговорено иное).
В начале и конце каждой строки допускаются пробелы.
Все задачи должны решаться при помощи рекурсивного генератора или рекурсивной функции.
Генераторы должны по одному возвращать списки с числами, рекурсивные функции — списки всех списков с числами.
Основная идея решений
Все задачи в этом листке решаются при помощи одной и той же идеи.
Пусть нам нужно перебрать все последовательности длины $n$ с какими-нибудь особыми свойствами.
Если ответ очевиден (например, если $n=1$ или особые свойства не оставляют выбора), то выдаём ответ.
В случае с генераторами по очереди делаем yield для всех последовательностей из очевидного ответа.
В случае с функцией собираем их все в список и этот список возвращаем.
В противном случае все последовательности длины $n$ можно получить приписывая в начало или в хвост последовательностей длины $n-1$ все возможные префиксы или суффиксы. Иногда нужно приписывать не в начало, а в середину.
Важный пример: хотим получить все двоичные последовательности длины $n$ в лексикографическом порядке.
Если $n=1$, то выдаём [0] и [1].
В противном случае начинаем с префикса [0] и приклеиваем к нему все последовательности длины $n-1$.
Затем берём префикс [1] и тоже последовательно приклеиваем все последовательности длины $n-1$.
Решение получилось не самое удачное: нам потребовалось дважды перебрать все последовательности длины $n-1$.
Можно сделать гораздо лучше: последовательно перебрать последовательности длины $n-1$, и для каждой подклеить в хвост сначала суффикс [0], а затем — суффикс [1]. Получится тоже верное решение, но выполняющее подперебор лишь один раз.
Генератор VS список списков
У каждого из подходов есть свои плюсы и минусы.
Бывают ситуации, что для создания последовательностей длины $n$ нужно несколько раз пройтись по последовательностям длины $n-1$. В таких ситуациях рекурсивная функция со списком списков будет на высоте, а решение с генератором потребует несколько одинаковых переборов.
Если этого не требуется, то сразу получаем основной плюс генераторов: они не требуют дополнительной памяти на хранение всех последовательностей.
Например, если нужно перебрать все последовательности длины 10, то в каждый момент времени генератор будет выдавать список из 10 чисел, храня внутри себя не так много данных.
Функция, возвращающая список списков, будет хранить $10 \cdot 10! = 36288000$ чисел, что потребует в питоне почти 1ГБ оперативной памяти.
Жирный минус генераторов появляется там, где нужно создавать очень длинные последовательности.
Если нужно выдать все последовательности длины 10000 с особым свойством, из-за которого таких последовательностей не слишком много, то рекурсивные генераторы здесь будут работать плохо: скорее всего у нас будет рекурсия глубины 10000, и на каждом уровне будет храниться какой-то суффикс или префикс выдаваемой последовательности, что потребует хранения $\frac{10000\cdot(10000-1)}{2}$ чисел (опять больше 1ГБ оперативной памяти).
Неаккуратное решение с функцией не исправляет эту проблему, но аккуратное решение по крайней мере не требует хитрых ухищрений.
Обычно для создания последовательностей длины $n$ нужно брать за основу последовательности длины $n-1$ целиком, создавая лишние копии только в тех случаях, когда это действительно нужно.
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 единиц в лексикографическом порядке.
Эту задачу нужно решить при помощи рекурсивного генератора.
Если $k=0$, $k=n$ или $k>n$, то всё просто. А иначе нужно сгенерить все последовательности длины $n-1$, в которых $k$ единиц, и к каждой добавить в конец 0.
А также сгенерить все последовательности длины $n-1$, в которых $k-1$ единиц, и к каждой добавить в конец 1.
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
Необязательные параметры
В некоторых случаях удобно создавать функции и генераторы с необязательным параметром:
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 = []
...
Общие объекты в рекурсивных функциях
Иногда требуется написать рекурсивную функцию, чтобы на любой глубине был доступ к какому-нибудь общему изменяемому объекту.
Сделать это можно при помощи необязательного параметра списка или словаря.
Код для просмотра и копирования
def rec_comb(n, *, _shared=None):
print(' Вошли. $n$ =', $n$, '_shared =', _shared)
is_initial = False
if _shared is None: # Это - начальный вызов
print(' Это --- начальный вызов')
_shared = []
is_initial = True
_shared.append(n)
if $n$ > 0:
print(' $n$ > 0, делаем рекурсивный вызов')
rec_comb(n - 1, _shared=_shared)
if is_initial:
print(' Это тот самый начальный вызов. Возвращаем ответ.')
return _shared
print(' Это не начальный вызов. Ничего не возвращаем')
print('Мы снаружи. Запускаем')
ans = rec_comb(3)
print(ans)
print('Мы снаружи. Завершаем работу')
"""
Мы снаружи. Запускаем
Вошли. $n$ = 3 _shared = None
Это --- начальный вызов
$n$ > 0, делаем рекурсивный вызов
Вошли. $n$ = 2 _shared = [3]
$n$ > 0, делаем рекурсивный вызов
Вошли. $n$ = 1 _shared = [3, 2]
$n$ > 0, делаем рекурсивный вызов
Вошли. $n$ = 0 _shared = [3, 2, 1]
Это не начальный вызов. Ничего не возвращаем
Это не начальный вызов. Ничего не возвращаем
Это не начальный вызов. Ничего не возвращаем
Это тот самый начальный вызов. Возвращаем ответ.
[3, 2, 1, 0]
Мы снаружи. Завершаем работу
"""
F: Двоичные последовательности длины $n$ содержащие не более $k$ единиц без двух единиц подряд
По данным натуральным n и k (0⩽k⩽n, n⩾1) выведите все двоичные строки длины n
содержащие не более k единиц и не содержащие двух единиц подряд в лексикографическом порядке.
Эту задачу нужно решить при помощи рекурсивного генератора.
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.
Эту задачу нужно решить при помощи рекурсивной функции.
Если $k=n$ или $k < n$, то всё просто. А иначе сгенерим все возрастающие последовательности длины $n-1$ из чисел $1\ldots(k-1)$.
Теперь попробуем добавить к каждой последовательности в хвост число $n$, затем число $n+1$ и так далее до $k$.
I: Убывающие последовательности
По данным натуральным n и k (n⩽k) выведите все убывающие последовательности длины n,
состоящие из чисел 1..k.
Эту задачу нужно решить при помощи рекурсивного генератора.
Если $k=n$ или $n=0$ то всё очевидно.
Иначе каждая наша последовательность может начинаться с чисел $k, k-1, \ldots, n$.
Обозначим это число через $st$.
Для каждого начала переберём рекурсивно все убывающие последовательности длины $n-1$ из чисел $1\ldots st-1$.
И к каждой в начало добавим $st$.
J: Разбиение на невозрастающие слагаемые
Дано натуральное число n. Выведите всевозможные его разбиения на слагаемые, упорядоченные в порядке невозрастания.
Сами разбиения необходимо выводить в лексикографическом порядке.
Эту задачу нужно решить при помощи рекурсивной функции.
5
1 1 1 1 1
2 1 1 1
2 2 1
3 1 1
3 2
4 1
5
Подсказка
Что-то туплю. Чес-слово!...
Если $n < 2$, то всё очевидно.
Иначе последовательно возьмём каждое разбиение числа $n - 1$ на невозрастающие слагаемые.
Припишем в конец суффикс [1], и, если это возможно, прибавим к последнему элементу 1.
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 в лексикографическом порядке.
Дано натуральное числo n. Выведите все правильные скобочные последовательности, состоящие из
n открывающихся скобок и n закрывающихся скобок в лексикографическом порядке. Используются круглые и квадратные скобки,
их порядок следующий:
( < ) < [ < ]
2
(())
()()
()[]
([])
[()]
[[]]
[]()
[][]
R★: Правильные скобочные последовательности - 3
Дано натуральное числo n. Выведите $k$ первых в лексикографическом порядке правильных скобочных последовательности, состоящих из
n открывающихся скобок и n закрывающихся скобок в лексикографическом порядке. Используются круглые, квадратные и фигурные скобки.
Лексикографичесчкий порядок для скобок задается в тестовых данных.
Программа получает на вход число n - количество открывающихся скобочек в исходной последовательности,
количество правильных скобочных последовательностей k, которые необходимо вывести (nk⩽106).
Затем идет строка из 6 символов, являющаяся некоторой перестановкой строки "()[]{}", задающая лексикографический порядок.
Гарантируется, что существует k правильных последовательностей указанной длины.