Задача по составлению цепочки слов

При прохождении курса Java.Multithreading меня очень заинтересовала задача по составлению цепочки слов: https://javarush.com/tasks/com.javarush.task.task22.task2209. Сама задача: дана цепочка слов, необходимо их упорядочить таким образом, чтобы для каждой пары слов последняя буква первого слова совпадала с первой буквой следующего. Естественно, в итоговую цепочку должны войти по 1 разу все слова оригинальной цепочки. Например "Киев Нью-Йорк Амстердам Вена Мельбурн" -> "Амстердам Мельбурн Нью-Йорк Киев Вена" или "ab ac bc" -> "ab bc ca". Задача заинтересовала меня с точки зрения комбинаторики и нахождения решения. <h2>1. Алгоритм</h2><h3>1.1. Перебор</h3>Самый простой, приходящий в голову алгоритм — перебор всех возможных комбинаций до нахождения нужной. Главный минус - резкое и ускоряющееся нарастание количества комбинаций - количество комбинаций для n слов будет равно факториалу и сложность алгоритма O(n!). Для 3 слов получается такой набор - 6 комбинаций: Для 4 слов: Википедия подсказывает, что для 10 слов будет 3,2 млн комбинаций, а для 100 слов - ~10^158 комбинаций. Перебрать такое количество комбинаций выглядит несколько... затруднительным... <h3>1.2. Наращение</h3>Итак, нужен какой-то другой алгоритм, а не просто перебор, например, последовательного присоединения: (1) Взять первое слово, (2) Берем следующее и пробуем присоединить его (слева или справа) к первому. Если получилось - повторить для всех оставшихся слов. (3) Если исходный список пуст - мы нашли последовательность, если не пуст - неудача, переходим к (4) (4) Берем в качестве начального не первое, а второе слово итд. Если я не ошибаюсь, сложность этого алгоритма O(n^2), что намного меньше первого. Проблема его в том, что могут быть последовательности (достаточно длинные), для которых начало с любого символа не приводит к решению - строка закольцовывается и оставшиеся символы не могут быть присоединены. В принципе, далее возможны варианты — если не удалось, можно пойти в обратном порядке (реверсировать строку и начать сначала), либо случайно перемешать слова, итд. Это похоже на игру в наперстки — если не получилось, пробуем перемешивать кубики в ящике до тех пор, пока не получится нужной последовательности. Сколько это займет времени и получится ли - непонятно. <h3>1.3. Циклические последовательности</h3>В основе этого алгоритма лежит простая идея: если у нас есть 2 удовлетворяющих условию задачи последовательности - они могут быть соединены в одну, если содержат пересекающиеся символы. И алгоритм будет такой: (1) Разбить исходную последовательность на x минимальных циклических последовательностей, удовлетворяющих условиям задачи (2) Объединить циклические последовательности в одну итоговую последовательность, удовлетворяющую условиям задачи. Стоит заметить, что слова, содержащие одинаковые первую и последнюю буквы в этом случае можно рассматривать как минимальные циклические последовательности. И их можно как присоединять к другим словам на этапе (1), так и оставить на этап (2). <h2>2. Реализация</h2>Код выложен на github, далее при необходимости буду упоминать [функции], которые реализуют описываемую задачу. <h3>2.1. Элементарный кирпичик</h3>При реализации придется очень часто обращаться к первой и последней буквам слова, поэтому в качестве элементарного кирпичика использовался класс, содержащий помимо самого слова также его первую и последнюю буквы:

class Word {
    private final String string;
    private final char firstLetter;
    private final char lastLetter;

    Word(String string) {
        this.string = string;
        firstLetter = Character.toLowerCase(string.charAt(0));
        lastLetter = Character.toLowerCase(string.charAt(string.length() - 1));
    }
}

<h3>2.2. Проверка исходной последовательности</h3>Перед тем, как начинать основной алгоритм поиска, стоит убедиться, что задача в принципе разрешима. Я это реализовывал с помощью следующих проверок (далее в этом пункте S - это исходная строка, W - массив Word, созданный на ее основе):

1. S не null, длина S > 0 (ну, это очевидно)
2. В W количество и типы первых и последних символов совпадают [checkLetters()].
   Например, строка "ab ba" разрешима и содержит firstLetters = {a=1, b=1}, lastLetters = {a=1, b=1},
   А строка "ab ba bc" неразрешима и содержит firstLetters = {a=1, b=2}, lastLetters = {a=1, b=1, c=1}.
   
3. Все слова в W связны между собой [checkConnectivity()]. Например, слово "ab" обеспечивает связность [a,b], в последовательности "ab bc cd da" связные символы [a,b,c,d], обе эти последовательности разрешимы. А вот последовательность "ab bc ca fg gf" неразрешима и содержит 2 несвязных блока: {[a,b,c] и [f,g]}. Проверял связность я с помощью List<set<character>> следующим образом:
   • 3.1. Берем любое слово, проверяем содержатся ли его первый/последний символы в каком-либо Set<character>
   • 3.2. Если ни один из Set<character> не содержит его первой или последней буквы - создаем новый Set<character> с ними
   • 3.3. Если только 1 Set<character> содержит его первую/последнюю букву - добавляем другую букву в этот Set
   • 3.4. Если 1 сет содержит первую букву, а второй последнюю - объединяем эти сеты
   • 3.5. Повторить для всех слов
   • 3.6. Если в итоге List<set<character>> содержит только 1 сет - последовательность связна, если больше 1 - то не связна и не разрешима.

<h3>2.3. Поиск финальной последовательности [generateResultLists()]</h3>Для поиска пришлось создать дополнительный класс CycleList, который содержит List<word>, удовлетворяющий условиям задачи, а также Set<character>, в котором содержится множество символов из List<words>. Главная "фишка" этого класса - его способность к перегруппировке таким образом, чтобы List начинался (и заканчивался) с любой необходимой буквы, входящей в Set<character>. Например, (regroup(b)) "ab bc ca" -> "bc ca ab". Это позволяет легко срастить 2 таких листа, имеющих пересечение по символам - достаточно их оба перегруппировать по пересекающемуся символу и можно один лист добавить в другой (далее описанный выше алгоритм реализуется достаточно легко).

private static class CycleList {
        List<word> list;
        Set<character> characterSet = new HashSet<>();

        public CycleList(List<word> list) {
            this.list = new ArrayList<>(list);
            list.forEach(w -> {
                characterSet.add(w.getFirstLetter());
                characterSet.add(w.getLastLetter());
            });
        }

        void regroup(char ch) {
            int first = 0;
            while (first++ < list.size())
                if (list.get(first).getFirstLetter() == ch) break;
            List<word> tempList = new ArrayList<>(list.size());
            list.stream().skip(first).forEachOrdered(tempList::add);
            list.stream().limit(first).forEachOrdered(tempList::add);
            list = tempList;
        }
    }

<h2>3. В заключение</h2>Задача мне весьма понравилась, пришлось поломать голову с точки зрения алгоритма, но нисколько об этом не жалею. Причесывая получившийся код стал лучше понимать работу с лямбда-выражениями и коллекциями в Java. Описанный код работает достаточно бодро, на моем, уже не молодом ПК, массив из 30 000 случайных слов упорядочивается примерно за 1 секунду. Код на гитхабе кроме описанного решения также содержит:

1. Генератор случайных последовательностей
2. Класс SequenceAlgorithm, который реализует алгоритм из раздела (1.2)
3. Несколько последовательностей для тестирования, например, моя реализация SequenceAlgorithm не находит решения для такой последовательности (ни в прямом, ни в обратном направлении): LK Ud aa LL WY OK lQ cK MK MM UU ll kk ss LJ HH dU dI aQ HJ ky ik mL MW jT KO JL lz ki Us WW QQ zl jj KK Id yk sU YW WB Ql KL JJ LL KK Tj JH OO ll Kc WM KM kk aC Lm Qa dd BW Ca WW