Tâche de chaîne de mots

En suivant le cours Java.Multithreading, j'étais très intéressé par la tâche de composer une chaîne de mots : https://javarush.com/tasks/com.javarush.task.task22.task2209 . La tâche elle-même : étant donné une chaîne de mots, il faut les ordonner de telle sorte que pour chaque paire de mots la dernière lettre du premier mot coïncide avec la première lettre du suivant. Naturellement, la chaîne finale doit comprendre une seule fois tous les mots de la chaîne originale. Par exemple, « Kiev New York Amsterdam Vienne Melbourne » -> « Amsterdam Melbourne New York Kiev Vienne » ou « ab ac bc » -> « ab bc ca ». Le problème m'intéressait du point de vue de la combinatoire et de la recherche d'une solution. <h2>1. Algorithme</h2><h3>1.1. Force brute</h3>L'algorithme le plus simple qui vient à l'esprit consiste à rechercher toutes les combinaisons possibles jusqu'à ce que celle souhaitée soit trouvée. Le principal inconvénient est une augmentation forte et accélérée du nombre de combinaisons - le nombre de combinaisons pour n mots sera égal à la factorielle et la complexité de l'algorithme est O(n !). Pour 3 mots, on obtient l'ensemble suivant - 6 combinaisons : Pour 4 mots : Wikipédia suggère que pour 10 mots il y aura 3,2 millions de combinaisons, et pour 100 mots - ~10^158 combinaisons. Passer par un tel nombre de combinaisons semble quelque peu... difficile... <h3>1.2. Incrément</h3>Donc, nous avons besoin d'un autre algorithme, et pas seulement d'une énumération, par exemple, d'une jointure séquentielle : (1) Prenez le premier mot, (2) Prenez le suivant et essayez de le joindre (à gauche ou à droite ) au premier. Si cela fonctionne, répétez pour tous les mots restants. (3) Si la liste initiale est vide, on a trouvé la suite ; si elle n'est pas vide, échec, passer à (4) (4) On prend comme mot initial non pas le premier, mais le second, etc. Si je ne me trompe pas, la complexité de cet algorithme est O(n^2), ce qui est bien moindre que le premier. Le problème est qu'il peut y avoir des séquences (assez longues) pour lesquelles commencer par n'importe quel caractère ne conduit pas à une solution - la ligne devient une boucle et les caractères restants ne peuvent pas être ajoutés. En principe, d'autres options sont possibles - si cela ne fonctionne pas, vous pouvez procéder dans l'ordre inverse (inverser la ligne et recommencer), ou mélanger les mots au hasard, etc. C'est comme jouer aux dés à coudre : si cela ne fonctionne pas, nous essayons de mélanger les cubes dans la boîte jusqu'à obtenir la séquence souhaitée. On ne sait pas combien de temps cela prendra et si cela fonctionnera. <h3>1.3. Séquences cycliquesCet algorithme repose sur une idée simple : si nous avons 2 séquences qui satisfont aux conditions du problème, elles peuvent être combinées en une seule si elles contiennent des caractères qui se croisent. Et l'algorithme sera comme ceci : (1) Divisez la séquence originale en x séquences cycliques minimales qui satisfont aux conditions du problème (2) Combinez les séquences cycliques en une séquence finale qui satisfait aux conditions du problème. Il convient de noter que les mots contenant les mêmes première et dernière lettres dans ce cas peuvent être considérés comme des séquences cycliques minimales. Et ils peuvent soit être attachés à d'autres mots à l'étape (1), soit laissés à l'étape (2). <h2>2. Implémentation</h2>Le code est publié sur github , en outre, si nécessaire, je mentionnerai les [fonctions] qui implémentent la tâche décrite. <h3>2.1. Brique élémentaire</h3>Lors de l'implémentation, vous devrez très souvent faire référence à la première et à la dernière lettre d'un mot, c'est pourquoi une classe contenant, en plus du mot lui-même, également ses première et dernière lettres a été utilisée comme brique élémentaire :

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. Vérification de la séquence d'origine</h3>Avant de démarrer l'algorithme de recherche principal, vous devez vous assurer que le problème est, en principe, résoluble. J'ai implémenté cela en utilisant les vérifications suivantes (ci-après dans ce paragraphe, S est la chaîne source, W est le tableau Word créé sur cette base) :

1. S n'est pas nul, longueur S > 0 (enfin, c'est évident)
2. Dans W, le nombre et les types de premier et dernier caractères sont les mêmes [checkLetters()] .
   Par exemple, la chaîne "ab ba" peut être résolue et contient firstLetters = {a=1, b=1}, lastLetters = {a=1, b=1}, et la chaîne "ab ba bc" est indécidable et contient firstLetters = {a=
   1 , b=2 }, dernièresLettres = {a=1, b=1, c=1 }.
   
3. Tous les mots de W sont connectés les uns aux autres [checkConnectivity()] . Par exemple, le mot "ab" fournit la connexité [a,b], dans la séquence "ab bc cd da" les symboles connectés [a,b,c,d], ces deux séquences sont décidables. Mais la séquence "ab bc ca fg gf" est insoluble et contient 2 blocs déconnectés : {[a,b,c] et [f,g]}. J'ai vérifié la connectivité en utilisant List<set<character>> comme suit :
   • 3.1. Nous prenons n'importe quel mot, vérifions si ses premier/dernier caractères sont contenus dans un Set<character>
   • 3.2. Si aucun des Set<character> ne contient sa première ou sa dernière lettre, créez un nouveau Set<character> avec eux
   • 3.3. Si seulement 1 Set<character> contient sa première/dernière lettre - ajoutez une autre lettre à cet Set
   • 3.4. Si 1 ensemble contient la première lettre, et la seconde la dernière, on combine ces ensembles
   • 3.5. Répétez pour tous les mots
   • 3.6. Si à la fin List<set<character>> ne contient qu'un seul ensemble, la séquence est connectée , si elle est supérieure à 1, alors elle n'est pas connectée et ne peut pas être résolue.

<h3>2.3. Rechercher la séquence finale [generateResultLists()]</h3>Pour effectuer la recherche, nous avons dû créer une classe supplémentaire CycleList, qui contient un List<word> qui satisfait aux conditions de la tâche, ainsi qu'un Set<character>, qui contient de nombreux caractères de List<words>. La principale "caractéristique" de cette classe est sa capacité à se réorganiser de manière à ce que la liste commence (et se termine) par n'importe quelle lettre nécessaire incluse dans Set<character>. Par exemple, (regroup(b)) "ab bc ca" -> "bc ca ab". Cela vous permet de fusionner facilement 2 de ces feuilles qui ont une intersection de symboles - il suffit de les regrouper toutes les deux par le symbole qui se croise et vous pouvez ajouter une feuille à l'autre (l'algorithme décrit ci-dessus est implémenté assez facilement).

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. En conclusionJ'ai beaucoup aimé le problème, j'ai dû me creuser la tête du point de vue de l'algorithme, mais je ne le regrette pas du tout. En parcourant le code résultant, j'ai commencé à mieux comprendre le travail avec les expressions et les collections lambda en Java. Le code décrit fonctionne assez rapidement : sur mon PC qui n'est plus jeune, un tableau de 30 000 mots aléatoires est trié en 1 seconde environ. En plus de la solution décrite, le code sur Github contient également :

1. Générateur de séquence aléatoire
2. La classe SequenceAlgorithm, qui implémente l'algorithme de la section (1.2)
3. Plusieurs séquences à tester, par exemple mon implémentation de SequenceAlgorithm ne trouve pas de solution pour cette séquence (ni avant ni arrière) : 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