Доброго времени суток, читатели, зрители моего канала programmer's notes. Не забывайте подписываться и писать свои комментарии к моим статьям и видео.
Пример комбинаторной задачи, обобщающей задачу генерацию перестановок на Python
Вспомнилась мне олимпиадная задача. Автором был её я. Когда я её решил, я вдруг обнаружил, что задача поиска всех перестановок является частным случаем данной задачи. В общем чисто комбинаторная красивая задачка.
И так дано несколько слов. Эти слова могут образовывать цепочки по принципу:
1. Цепочка может начинаться с любого из слов.
2. Последующие слова начинаются с буквы, которой заканчивается предыдущее слово.
3. Слова из заданных могут встретиться в данной цепочке только один раз.
На таком принципе построения цепочек можно решать разные задачи. Предположим мы имеем набор слов. Поставим вопрос найти все возможные цепочки. Пусть имеются слова
abc
abz
era
Тогда все цепочки будут
abc
abz
era abc
era abz
era
Ниже представлена программа решения подобной задачи. Данные берутся с внешнего потока (файла). Кто помнит мою программу о перестановках, то данная программа очень на неё похожа. Подход тот же во всяком случае. Список ls2 служит для накопления цепочки, параметр k после окончания цикла внутри рекурсивной функции определяет длину цепочки, ls1 содержит исходные слова. Каждый элемент ls1 двухкомпонентный. Первый компонент это само слово, второй признак того, что слово уже поучаствовало в формировании данной цепочки.
Заметим, что если в наборе все слова начинаются и заканчиваются на одну букву, то среди получившихся цепочек самые длинные это перестановки слов. Чтобы получить перестановки таким образом нужно просто отбросить все более короткие цепочки.
Можно усовершенствовать предыдущую программу, точнее рекурсивную функцию. См. программу ниже.
Рекурсивная функция имеет второй параметр. Если параметр равен 0, то функция накапливает длину цепочек в переменной m. Таким образом после окончания работы переменная будет содержать длину самой длинной цепочки. При запуске рекурсивной функции со вторым параметром равны равным 1, функция будет выводить все цепочки заданной длины. Длина хранится в переменно m. В нашем случае мы получим все самые длинные цепочки, но, в принципе, можно таким образом получать цепочки просто заданной длины. Наконец, если все слова на входе начинаются или заканчиваются с одной и той же буквы, то наша программа выдаст все возможные перестановки слов.
Замечание
В решении выше рекурсивная функция вызывается дважды. А можно ли решить её одним вызовом? Конечно. Просто, сохранять в памяти промежуточные максимумы: сохраняются все цепочки временно-максимальной длины. Если появляется цепочка такой-же длины, то она добавляется к набору, если длина будет больше, то создаётся новый набор, если длина меньше, то цепочка игнорируется. В общем принцип очевиден, главное, чтобы памяти хватило. Но в целом для больших переборов алгоритм должен работать, конечно, быстрее. Попробуйте написать, я как-то пока поленился.
Хорошего программирования. Оставляйте свои комментарии, не забывайте про лайки и подписывайтесь на мой канал programmer's notes.