0

Условие задачи: вывести все возможные последовательности городов, которые удовлетворяют условию: последняя буква текущего слова соответствует первой букве следующего. Я использую список из N городов, записываю в файл последовательности городов через пробел. Сами последовательности разделены \n. Я хочу реализовать проход по всем словам в списке, которые бы инициализировали старт цикла, который бы создавал последовательности, инициализированные этим словом. Например:

[milltimber, ringwood, dundonald, londonderry, ystrad]

Выходные последовательности:

milltimber ringwood dundonald
ringwood dundonald
londonderry ystrad dundonald
ystrad dundonald

Моя реализация такова:

for city_1 in cities_list:  
    создаем список cities_list_iterable и удаляем из него city_1 
    for city_2 in cities_list_iterable:
        Проверяем, совпадает ли первая буква city_2 с последней буквой city_1, и если да:
            добавляем city_2 в текущую последовательность, удаляем его из cities_list_iterable
            присваиваем city_1 значение city_2

Однако при такой реализации нам необходимо вернутся в начало цикла for city_2 in cities_list_iterable: что бы снова начать проверять все ещё не удалённые города на соответствие условию. Я не понимаю как это сделать. Также я не уверен в правильности этого алгоритма, а также в его оптимальности. Я раздумывал над решением через графы, но не совсем понял, как найти в данном случае все последовательности. Оптимальность алгоритма важна, поэтому прошу подсказать также другие варианты решения задачи.

2
  • что, если после "milltimber" есть не один, а несколько городов, названия которых начинается на "r"?
    – Jack_oS
    25 мар 2021 в 16:26
  • По-хорошему надо перебрать их всех. Но давайте для начала разберемся с тем случаем, когда мы записываем первое попавшееся слово. Хотя если алгоритм будет рассматривать все последовательности, это будет только + 25 мар 2021 в 16:37

1 ответ 1

2

Ваша задача относится к классу задач поиска путей на графе.

Для начала строим матрицу смежности между узлами-словами. Узлы связаны между собой направленной связью если слово в исходящем узле заканчивается на ту-же букву, что начинается слово в узле, в который это ребро направлено.

После этого забываем про слова, а работаем только с матрицей. Перебираем все вершины и из каждой строим все возможные цепочки-пути, последовательно наращивая слои.

Поскольку никаких ограничений у вас нет, то это просто переборная задача. Алгоритм скорее всего получится рекурсивный.

Вот примерно как-то так. Возможно даже удастся найти готовую реализацию.

2
  • Подскажите, пожалуйста, как сгенерировать матрицу смежности, имея список слов. 27 мар 2021 в 18:54
  • А вы встречались с понятием "матрица смежности"? Это такая матрица, каждая строка и каждый столбец которой соответствует слову в вашем наборе, а элементы равны "1", если первое слово заканчивается буквой, на которуе начинается второе слово и "0" - в противном случае. Строиться такая матрица перебором элементов списка слов. Двойным циклом, если что.
    – passant
    27 мар 2021 в 19:05

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.