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 you have read our privacy policy.

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