Zadanie z łańcuszkiem słów

Podczas kursu Java.Multithreading bardzo zainteresowało mnie zadanie ułożenia łańcucha słów: https://javarush.com/tasks/com.javarush.task.task22.task2209 . Samo zadanie: mając łańcuch słów, należy je uporządkować w taki sposób, aby dla każdej pary słów ostatnia litera pierwszego słowa pokrywała się z pierwszą literą następnego. Oczywiście końcowy łańcuch musi zawierać raz wszystkie słowa oryginalnego łańcucha. Na przykład „Kijów Nowy Jork Amsterdam Wiedeń Melbourne” -> „Amsterdam Melbourne Nowy Jork Kijów Wiedeń” lub „ab ac bc” -> „ab bc ca”. Problem zainteresował mnie z punktu widzenia kombinatoryki i znalezienia rozwiązania. <h2>1. Algorytm</h2><h3>1.1. Brutalna siła</h3>Najprostszym algorytmem, jaki przychodzi na myśl, jest przeszukiwanie wszystkich możliwych kombinacji, aż do znalezienia pożądanej. Główną wadą jest gwałtowny i przyspieszający wzrost liczby kombinacji - liczba kombinacji dla n słów będzie równa silni, a złożoność algorytmu wyniesie O(n!). Dla 3 słów otrzymujemy następujący zestaw - 6 kombinacji: Dla 4 słów: Wikipedia sugeruje, że dla 10 słów będzie 3,2 miliona kombinacji, a dla 100 słów - ~10^158 kombinacji. Przejście przez taką liczbę kombinacji wydaje się nieco... trudne... <h3>1.2. Inkrementacja</h3>Potrzebujemy więc innego algorytmu, a nie tylko wyliczania, na przykład łączenia sekwencyjnego: (1) Weź pierwsze słowo, (2) Weź następne i spróbuj je połączyć (po lewej lub prawej stronie ) do pierwszego. Jeśli to zadziała, powtórz dla wszystkich pozostałych słów. (3) Jeśli początkowa lista jest pusta, znaleźliśmy sekwencję; jeśli nie jest pusta, oznacza to niepowodzenie, przejdź do (4) (4) Za słowo początkowe bierzemy nie pierwsze, ale drugie itd. Jeśli się nie mylę, złożoność tego algorytmu wynosi O(n^2), czyli jest znacznie mniejsza niż pierwszego. Problem w tym, że mogą pojawić się ciągi (dość długie), dla których rozpoczęcie od dowolnego znaku nie prowadzi do rozwiązania - linia zapętla się i nie można dopisać pozostałych znaków. W zasadzie możliwe są dalsze opcje – jeśli to nie zadziała, możesz zastosować odwrotną kolejność (odwrócić linię i zacząć od nowa) lub losowo wymieszać słowa itp. Przypomina to grę w naparstki – jeśli nam nie wychodzi, staramy się mieszać kostki w pudełku, aż uzyskamy pożądaną sekwencję. Nie wiadomo, jak długo to zajmie i czy zadziała. <h3>1.3. Ciągi cykliczneAlgorytm ten opiera się na prostym pomyśle: jeśli mamy 2 ciągi spełniające warunki zadania, można je połączyć w jeden, jeśli zawierają przecinające się znaki. Algorytm będzie wyglądał następująco: (1) Podziel pierwotny ciąg na x minimalnych ciągów cyklicznych spełniających warunki zadania (2) Połącz ciągi cykliczne w jeden końcowy ciąg, który spełnia warunki zadania. Warto zauważyć, że słowa zawierające tę samą pierwszą i ostatnią literę w tym przypadku można uznać za minimalne ciągi cykliczne. Można je albo dołączyć do innych słów na etapie (1), albo pozostawić na etapie (2). <h2>2. Implementacja</h2>Kod zamieszczono na githubie , dalej w razie potrzeby wspomnę o [funkcjach] realizujących opisywane zadanie. <h3>2.1. Cegła elementarna</h3>Podczas realizacji będziesz musiał bardzo często odwoływać się do pierwszej i ostatniej litery słowa, dlatego jako elementarna cegła została wykorzystana klasa zawierająca oprócz samego słowa także jego pierwszą i ostatnią literę :

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. Sprawdzanie oryginalnej sekwencji</h3>Przed uruchomieniem głównego algorytmu wyszukiwania należy upewnić się, że problem jest w zasadzie możliwy do rozwiązania. Zaimplementowałem to, stosując następujące kontrole (w dalszej części tego akapitu S to ciąg źródłowy, W to utworzona na jego podstawie tablica Worda):

1. S nie jest zerowe, długość S > 0 (cóż, to oczywiste)
2. W W liczba i typy pierwszego i ostatniego znaku są takie same [checkLetters()] .
   Na przykład ciąg „ab ba” jest rozwiązywalny i zawiera pierwsze litery = {a=1, b=1}, ostatnie litery = {a=1, b=1}, a ciąg „ab ba bc” jest nierozstrzygalny i zawiera pierwsze litery = {a=
   1 , b=2 }, lastLetters = {a=1, b=1, c=1 }.
   
3. Wszystkie słowa w W są ze sobą połączone [checkConnectivity()] . Na przykład słowo „ab” zapewnia spójność [a, b], w sekwencji „ab bc cd da” połączone symbole [a, b, c, d], oba te ciągi są rozstrzygalne. Ale ciąg „ab bc ca fg gf” jest nierozwiązalny i zawiera 2 odłączone bloki: {[a,b,c] i [f,g]}. Sprawdziłem łączność za pomocą List<set<character>> w następujący sposób:
   • 3.1. Bierzemy dowolne słowo i sprawdzamy, czy jego pierwszy/ostatni znak zawiera się w jakimkolwiek zestawie <znak>
   • 3.2. Jeśli żaden z Set<character> nie zawiera swojej pierwszej ani ostatniej litery - utwórz z nimi nowy Set<character>
   • 3.3. Jeśli tylko 1 Zestaw<znak> zawiera swoją pierwszą/ostatnią literę - dodaj kolejną literę do tego Zestawu
   • 3.4. Jeśli 1 zestaw zawiera pierwszą literę, a drugi ostatnią, łączymy te zestawy
   • 3.5. Powtórz dla wszystkich słów
   • 3.6. Jeśli na końcu Lista<zbiór<znak>> zawiera tylko 1 zestaw, sekwencja jest połączona , jeśli jest ich więcej niż 1, to nie jest połączona i nie można jej rozwiązać.

<h3>2.3. Wyszukaj końcową sekwencję [generateResultLists()]</h3>Aby przeprowadzić wyszukiwanie, musieliśmy stworzyć dodatkową klasę CycleList, która zawiera List<word> spełniającą warunki zadania, a także Set<character>, który zawiera wiele znaków z List<words>. Główną „cechą” tej klasy jest jej zdolność do zmiany układu, tak aby Lista zaczynała się (i kończyła) dowolną niezbędną literą zawartą w Set<character>. Na przykład (przegrupuj(b)) „ab bc ca” -> „bc ca ab”. Pozwala to na łatwe połączenie 2 takich arkuszy, które mają przecięcie symboli - wystarczy przegrupować oba po przecinającym się symbolu i można dodać jeden arkusz do drugiego (opisany powyżej algorytm jest dość łatwy w implementacji).

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. Podsumowując, problem bardzo mi się spodobał, musiałem się nieźle namęczyć z punktu widzenia algorytmu, ale wcale tego nie żałuję. Przeczesując powstały kod, zacząłem lepiej rozumieć pracę z wyrażeniami lambda i kolekcjami w Javie. Opisany kod działa dość szybko; na moim już nie młodym komputerze PC tablica 30 000 losowych słów jest sortowana w około 1 sekundę. Oprócz opisanego rozwiązania, kod na Githubie zawiera także:

1. Generator sekwencji losowych
2. Klasa SequenceAlgorithm, która implementuje algorytm z rozdziału (1.2)
3. Kilka sekwencji do przetestowania, na przykład moja implementacja SequenceAlgorithm nie znajduje rozwiązania dla tej sekwencji (ani do przodu, ani do tyłu): 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