Во всех задачах этого листка необходимо сгенерировать все числовые последовательности, удовлетворяющие условию,
в лексикографическом порядке.
Ввод-вывод стандартный.
Каждая последовательность должна выводиться в отдельной строке, вывод должен завершаться символом новой строки.
Числа, входящие в последовательность, должны быть разделены одним пробелом (если в условии не оговорено иное).
В начале и конце каждой строки допускаются пробелы.
Все задачи должны решаться при помощи рекурсивного генератора или рекурсивной функции.
Генераторы должны по одному возвращать списки с числами, рекурсивные функции — списки всех списков с числами.
Все задачи в этом листке решаются при помощи одной и той же идеи.
Пусть нам нужно перебрать все последовательности длины n с какими-нибудь особыми свойствами.
Если ответ очевиден (например, если n=1 или особые свойства не оставляют выбора), то выдаём ответ.
В случае с генераторами по очереди делаем yield для всех последовательностей из очевидного ответа.
В случае с функцией собираем их все в список и этот список возвращаем.
В противном случае все последовательности длины n можно получить приписывая в начало или в хвост последовательностей длины n−1 все возможные префиксы или суффиксы. Иногда нужно приписывать не в начало, а в середину.
Важный пример: хотим получить все двоичные последовательности длины n в лексикографическом порядке.
Если n=1, то выдаём [0] и [1].
В противном случае начинаем с префикса [0] и приклеиваем к нему все последовательности длины n−1.
Затем берём префикс [1] и тоже последовательно приклеиваем все последовательности длины n−1.
Решение получилось не самое удачное: нам потребовалось дважды перебрать все последовательности длины n−1.
Можно сделать гораздо лучше: последовательно перебрать последовательности длины n−1, и для каждой подклеить в хвост сначала суффикс [0], а затем — суффикс [1]. Получится тоже верное решение, но выполняющее подперебор лишь один раз.
Бывают ситуации, что для создания последовательностей длины n нужно несколько раз пройтись по последовательностям длины n−1. В таких ситуациях рекурсивная функция со списком списков будет на высоте, а решение с генератором потребует несколько одинаковых переборов.
Если этого не требуется, то сразу получаем основной плюс генераторов: они не требуют дополнительной памяти на хранение всех последовательностей.
Например, если нужно перебрать все последовательности длины 10, то в каждый момент времени генератор будет выдавать список из 10 чисел, храня внутри себя не так много данных.
Функция, возвращающая список списков, будет хранить 10⋅10!=36288000 чисел, что потребует в питоне почти 1ГБ оперативной памяти.
Жирный минус генераторов появляется там, где нужно создавать очень длинные последовательности.
Если нужно выдать все последовательности длины 10000 с особым свойством, из-за которого таких последовательностей не слишком много, то рекурсивные генераторы здесь будут работать плохо: скорее всего у нас будет рекурсия глубины 10000, и на каждом уровне будет храниться какой-то суффикс или префикс выдаваемой последовательности, что потребует хранения 210000⋅(10000−1) чисел (опять больше 1ГБ оперативной памяти).
Неаккуратное решение с функцией не исправляет эту проблему, но аккуратное решение по крайней мере не требует хитрых ухищрений.
Обычно для создания последовательностей длины n нужно брать за основу последовательности длины n−1 целиком, создавая лишние копии только в тех случаях, когда это действительно нужно.
Если k=0, k=n или k>n, то всё просто. А иначе нужно сгенерить все последовательности длины n−1, в которых k единиц, и к каждой добавить в конец 0.
А также сгенерить все последовательности длины n−1, в которых k−1 единиц, и к каждой добавить в конец 1.
IDE
E: Двоичные последовательности длины n содержащие k единиц
По данным натуральным n и k (0⩽k⩽n, n⩾1) выведите все двоичные
последовательности длины n, содержащие ровно k единиц в лексикографическом порядке.
Эту задачу нужно решить при помощи рекурсивной функции.
В некоторых случаях удобно создавать функции и генераторы с необязательным параметром:
defgen(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:
Иногда требуется написать рекурсивную функцию, чтобы на любой глубине был доступ к какому-нибудь общему изменяемому объекту.
Сделать это можно при помощи необязательного параметра списка или словаря.
Код для просмотра и копирования
defrec_comb(n, *, _shared=None):
print(' Вошли. $n$ =', $n$, '_shared =', _shared)
is_initial = Falseif _shared isNone: # Это - начальный вызов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 единиц и не содержащие двух единиц подряд в лексикографическом порядке.
Эту задачу нужно решить при помощи рекурсивной функции.
Если k=n или k<n, то всё просто. А иначе сгенерим все возрастающие последовательности длины n−1 из чисел 1…(k−1).
Теперь попробуем добавить к каждой последовательности в хвост число n, затем число n+1 и так далее до k.
Если k=n или n=0 то всё очевидно.
Иначе каждая наша последовательность может начинаться с чисел k,k−1,…,n.
Обозначим это число через st.
Для каждого начала переберём рекурсивно все убывающие последовательности длины n−1 из чисел 1…st−1.
И к каждой в начало добавим st.
Дано натуральное число 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.
Дано натуральное число n. Выведите всевозможные его разбиения на слагаемые, упорядоченные в порядке неубывания.
Сами разбиения необходимо выводить в лексикографическом порядке.
Эту задачу нужно решить при помощи рекурсивного генератора.
Даны натуральные числа n и k (1⩽k⩽n).
Выведите всевозможные разбиения числа n на kслагаемых, упорядоченных в порядке невозрастания.
Сами разбиения необходимо выводить в лексикографическом порядке.
Эту задачу нужно решить при помощи рекурсивной функции.
Даны натуральные числа n и k (1⩽k⩽n).
Выведите всевозможные разбиения числа n на kслагаемых, упорядоченных в порядке неубывания.
Сами разбиения необходимо выводить в лексикографическом порядке.
Эту задачу нужно решить при помощи рекурсивного генератора.
Дано натуральное числo n. Выведите все правильные скобочные последовательности, состоящие из
n открывающихся круглых скобок и n закрывающихся скобок в лексикографическом порядке.
3
((()))
(()())
(())()
()(())
()()()
IDE
P: Правильные скобочные последовательности вложенности не более k
Даны натуральные числа n и k. Выведите все правильные скобочные последовательности, состоящие из
n открывающихся круглых скобок и n закрывающихся скобок такие, что максимальная
вложенность не превосходит k в лексикографическом порядке.
Дано натуральное числo n. Выведите все правильные скобочные последовательности, состоящие из
n открывающихся скобок и n закрывающихся скобок в лексикографическом порядке. Используются круглые и квадратные скобки,
их порядок следующий:
Дано натуральное числo n. Выведите k первых в лексикографическом порядке правильных скобочных последовательности, состоящих из
n открывающихся скобок и n закрывающихся скобок в лексикографическом порядке. Используются круглые, квадратные и фигурные скобки.
Лексикографичесчкий порядок для скобок задается в тестовых данных.
Программа получает на вход число n - количество открывающихся скобочек в исходной последовательности,
количество правильных скобочных последовательностей k, которые необходимо вывести (nk⩽106).
Затем идет строка из 6 символов, являющаяся некоторой перестановкой строки "()[]{}", задающая лексикографический порядок.
Гарантируется, что существует k правильных последовательностей указанной длины.