Aufgabe zur Wortkette

Während ich den Java.Multithreading-Kurs belegte, interessierte ich mich sehr für die Aufgabe, eine Wortkette zu erstellen: https://javarush.com/tasks/com.javarush.task.task22.task2209 . Die Aufgabe selbst: Bei einer vorgegebenen Wortkette gilt es, diese so anzuordnen, dass bei jedem Wortpaar der letzte Buchstabe des ersten Wortes mit dem ersten Buchstaben des nächsten übereinstimmt. Natürlich muss die letzte Kette alle Wörter der ursprünglichen Kette einmal enthalten. Zum Beispiel „Kiew New York Amsterdam Wien Melbourne“ -> „Amsterdam Melbourne New York Kiew Wien“ oder „ab ac bc“ -> „ab bc ca“. Das Problem interessierte mich aus kombinatorischer und lösungstechnischer Sicht. <h2>1. Algorithmus</h2><h3>1.1. Brute-Force</h3>Der einfachste Algorithmus, der mir in den Sinn kommt, ist das Durchsuchen aller möglichen Kombinationen, bis die gewünschte gefunden wird. Der Hauptnachteil ist ein starker und beschleunigter Anstieg der Anzahl der Kombinationen – die Anzahl der Kombinationen für n Wörter entspricht der Fakultät und die Komplexität des Algorithmus beträgt O(n!). Für 3 Wörter erhält man den folgenden Satz – 6 Kombinationen: Für 4 Wörter: Wikipedia geht davon aus, dass es für 10 Wörter 3,2 Millionen Kombinationen und für 100 Wörter ~10^158 Kombinationen gibt. Eine solche Anzahl an Kombinationen durchzugehen sieht etwas...schwierig aus... <h3>1.2. Erhöhen</h3>Wir brauchen also einen anderen Algorithmus und nicht nur eine Aufzählung, zum Beispiel eine sequentielle Verknüpfung: (1) Nehmen Sie das erste Wort, (2) Nehmen Sie das nächste und versuchen Sie, es zu verbinden (links oder rechts). ) zum ersten. Wenn es funktioniert, wiederholen Sie den Vorgang für alle verbleibenden Wörter. (3) Wenn die Anfangsliste leer ist, haben wir die Sequenz gefunden; wenn sie nicht leer ist, Fehler, gehen Sie zu (4) (4) Wir nehmen als Anfangswort nicht das erste, sondern das zweite usw. Wenn ich mich nicht irre, beträgt die Komplexität dieses Algorithmus O(n^2), was viel geringer ist als die des ersten. Das Problem besteht darin, dass es (ziemlich lange) Sequenzen geben kann, bei denen das Starten mit einem beliebigen Zeichen nicht zu einer Lösung führt – die Zeile wird in einer Schleife dargestellt und die restlichen Zeichen können nicht angehängt werden. Prinzipiell sind noch weitere Möglichkeiten möglich – wenn es nicht klappt, kann man in umgekehrter Reihenfolge vorgehen (Zeile umkehren und von vorne beginnen), oder die Wörter beliebig verwechseln usw. Das ist vergleichbar mit dem Spielen von Fingerhüten – wenn es nicht klappt, versuchen wir, die Würfel in der Schachtel zu vermischen, bis wir die gewünschte Reihenfolge haben. Wie lange es dauern wird und ob es funktionieren wird, ist unklar. <h3>1.3. Zyklische Sequenzen</h3>Dieser Algorithmus basiert auf einer einfachen Idee: Wenn wir zwei Sequenzen haben, die die Bedingungen des Problems erfüllen, können sie zu einer kombiniert werden, wenn sie sich überschneidende Zeichen enthalten. Und der Algorithmus sieht folgendermaßen aus: (1) Teilen Sie die ursprüngliche Sequenz in x minimale zyklische Sequenzen auf, die die Bedingungen des Problems erfüllen. (2) Kombinieren Sie die zyklischen Sequenzen zu einer endgültigen Sequenz, die die Bedingungen des Problems erfüllt. Es ist erwähnenswert, dass Wörter, die in diesem Fall denselben Anfangs- und Endbuchstaben enthalten, als minimale zyklische Sequenzen betrachtet werden können. Und sie können entweder in Stufe (1) an andere Wörter angehängt oder in Stufe (2) belassen werden. <h2>2. Implementierung</h2>Der Code ist auf Github veröffentlicht , außerdem werde ich bei Bedarf [Funktionen] erwähnen , die die beschriebene Aufgabe implementieren. <h3>2.1. Elementarer Baustein</h3>Während der Implementierung müssen Sie sehr oft auf den ersten und letzten Buchstaben eines Wortes verweisen, daher wurde als elementarer Baustein eine Klasse verwendet, die neben dem Wort selbst auch dessen ersten und letzten Buchstaben enthält :

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. Überprüfung der OriginalsequenzBevor Sie den Hauptsuchalgorithmus starten, sollten Sie sicherstellen, dass das Problem grundsätzlich lösbar ist. Ich habe dies mithilfe der folgenden Prüfungen implementiert (im Folgenden in diesem Absatz ist S die Quellzeichenfolge, W das darauf basierend erstellte Word-Array):

1. S ist nicht null, Länge S > 0 (nun, das ist offensichtlich)
2. In W sind Anzahl und Typ des ersten und letzten Zeichens gleich [checkLetters()] .
   Beispielsweise ist die Zeichenfolge „ab ba“ lösbar und enthält firstLetters = {a=1, b=1}, lastLetters = {a=1, b=1}. Und die Zeichenfolge „ab ba bc“ ist unentscheidbar und enthält firstLetters = {a=
   1 , b=2 }, lastLetters = {a=1, b=1, c=1 }.
   
3. Alle Wörter in W sind miteinander verbunden [checkConnectivity()] . Beispielsweise liefert das Wort „ab“ den Zusammenhang [a,b], in der Folge „ab bc cd da“ die Zusammenhangssymbole [a,b,c,d], beide Folgen sind entscheidbar. Aber die Sequenz „ab bc ca fg gf“ ist unlösbar und enthält 2 getrennte Blöcke: {[a,b,c] und [f,g]}. Ich habe die Konnektivität mit List<set<character>> wie folgt überprüft:
   • 3.1. Wir nehmen jedes Wort und prüfen, ob seine ersten/letzten Zeichen in einem Set<character> enthalten sind
   • 3.2. Wenn keines der Set<Zeichen> seinen ersten oder letzten Buchstaben enthält, erstellen Sie ein neues Set<Zeichen> mit diesen
   • 3.3. Wenn nur 1 Set<Zeichen> seinen ersten/letzten Buchstaben enthält, fügen Sie diesem Set einen weiteren Buchstaben hinzu
   • 3.4. Wenn ein Satz den ersten Buchstaben enthält und der zweite den letzten, kombinieren wir diese Sätze
   • 3.5. Wiederholen Sie dies für alle Wörter
   • 3.6. Wenn List<set<character>> am Ende nur 1 Satz enthält, ist die Sequenz zusammenhängend , wenn mehr als 1, dann ist sie nicht zusammenhängend und kann nicht aufgelöst werden.

<h3>2.3. Suche nach der endgültigen Sequenz [generateResultLists()]</h3>Zur Suche mussten wir eine zusätzliche Klasse CycleList erstellen, die ein List<word> enthält, das die Bedingungen der Aufgabe erfüllt, sowie ein Set<character>, die viele Zeichen aus der Liste<Wörter> enthält. Das Hauptmerkmal dieser Klasse ist ihre Fähigkeit, sie so neu anzuordnen, dass die Liste mit jedem erforderlichen Buchstaben beginnt (und endet), der im Set<Zeichen> enthalten ist. Zum Beispiel (regroup(b)) „ab bc ca“ -> „bc ca ab“. Auf diese Weise können Sie zwei solcher Blätter, die einen Schnittpunkt von Symbolen aufweisen, problemlos zusammenführen. Es reicht aus, beide anhand des Schnittpunktsymbols neu zu gruppieren, und Sie können ein Blatt dem anderen hinzufügen (der oben beschriebene Algorithmus lässt sich recht einfach implementieren).

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. Zusammenfassend lässt sich sagen, dass mir das Problem wirklich gut gefallen hat, ich musste mir aus Sicht des Algorithmus den Kopf zerbrechen, aber ich bereue es überhaupt nicht. Während ich den resultierenden Code durchforstete, begann ich, die Arbeit mit Lambda-Ausdrücken und -Sammlungen in Java besser zu verstehen. Der beschriebene Code funktioniert recht schnell; auf meinem nicht mehr jungen PC wird ein Array von 30.000 zufälligen Wörtern in etwa 1 Sekunde sortiert. Neben der beschriebenen Lösung enthält der Code auf Github auch:

1. Zufallssequenzgenerator
2. Die SequenceAlgorithm-Klasse, die den Algorithmus aus Abschnitt (1.2) implementiert
3. Mehrere Sequenzen zum Testen, zum Beispiel findet meine Implementierung von SequenceAlgorithm keine Lösung für diese Sequenz (weder vorwärts noch rückwärts): 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