Завдання зі складання ланцюжка слів

При проходженні курсу 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. Отже, потрібен якийсь інший алгоритм, а не просто перебір, наприклад, послідовного приєднання: (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 містить його першу/останню літеру - додаємо іншу літеру в цей Set
   • 3.4. Якщо 1 сет містить першу літеру, а другу останню – об'єднуємо ці сети
   • 3.5. Повторити всім слів
   • 3.6. Якщо в результаті List містить тільки 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 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