Tarea de cadena de palabras

Mientras tomaba el curso Java.Multithreading, me interesó mucho la tarea de componer una cadena de palabras: https://javarush.com/tasks/com.javarush.task.task22.task2209 . La tarea en sí: dada una cadena de palabras, es necesario ordenarlas de tal forma que para cada par de palabras la última letra de la primera palabra coincida con la primera letra de la siguiente. Naturalmente, la cadena final debe incluir todas las palabras de la cadena original una vez. Por ejemplo, "Kiev Nueva York Amsterdam Viena Melbourne" -> "Amsterdam Melbourne Nueva York Kiev Viena" o "ab ac bc" -> "ab bc ca". El problema me interesó desde el punto de vista de la combinatoria y la búsqueda de una solución. <h2>1. Algoritmo</h2><h3>1.1. Fuerza bruta</h3>El algoritmo más simple que me viene a la mente es buscar entre todas las combinaciones posibles hasta encontrar la deseada. La principal desventaja es un aumento brusco y acelerado en el número de combinaciones: el número de combinaciones para n palabras será igual al factorial y la complejidad del algoritmo es O(n!). Para 3 palabras, se obtiene el siguiente conjunto: 6 combinaciones: Para 4 palabras: Wikipedia sugiere que para 10 palabras habrá 3,2 millones de combinaciones, y para 100 palabras, ~10^158 combinaciones. Pasar por tal cantidad de combinaciones parece algo... difícil... <h3>1.2. Incremento</h3>Entonces, necesitamos algún otro algoritmo, y no solo una enumeración, por ejemplo, unión secuencial: (1) Tome la primera palabra, (2) Tome la siguiente e intente unirla (a la izquierda o a la derecha). ) al primero. Si funciona, repita con todas las palabras restantes. (3) Si la lista inicial está vacía, hemos encontrado la secuencia; si no está vacía, fallo, pasamos a (4) (4) Tomamos como palabra inicial no la primera, sino la segunda, etc. Si no me equivoco, la complejidad de este algoritmo es O(n^2), que es mucho menor que la del primero. El problema es que puede haber secuencias (bastante largas) en las que comenzar con cualquier carácter no conduce a una solución: la línea se convierte en un bucle y los caracteres restantes no se pueden agregar. En principio, son posibles más opciones: si no funciona, puedes ir en orden inverso (invertir la línea y empezar de nuevo), o mezclar palabras al azar, etc. Esto es similar a jugar con dedales: si no funciona, intentamos mezclar los cubos en la caja hasta obtener la secuencia deseada. No está claro cuánto tiempo llevará ni si funcionará. <h3>1.3. Secuencias cíclicas</h3>Este algoritmo se basa en una idea simple: si tenemos 2 secuencias que satisfacen las condiciones del problema, se pueden combinar en una si contienen caracteres que se cruzan. Y el algoritmo será así: (1) Dividir la secuencia original en x secuencias cíclicas mínimas que satisfagan las condiciones del problema (2) Combinar las secuencias cíclicas en una secuencia final que satisfaga las condiciones del problema. Vale la pena señalar que las palabras que contienen la misma primera y última letra en este caso pueden considerarse secuencias cíclicas mínimas. Y pueden adjuntarse a otras palabras en la etapa (1) o dejarse para la etapa (2). <h2>2. Implementación</h2>El código está publicado en github ; además, si es necesario, mencionaré [funciones] que implementan la tarea descrita. <h3>2.1. Ladrillo elemental</h3>Durante la implementación, tendrás que hacer referencia muy a menudo a la primera y la última letra de una palabra, por lo que se utilizó como ladrillo elemental una clase que contiene, además de la palabra en sí, también su primera y última letra. :

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. Comprobación de la secuencia original</h3>Antes de iniciar el algoritmo de búsqueda principal, debes asegurarte de que el problema es, en principio, solucionable. Implementé esto usando las siguientes comprobaciones (en adelante en este párrafo, S es la cadena fuente, W es la matriz de Word creada en base a ella):

1. S no es nulo, longitud S > 0 (bueno, eso es obvio)
2. En W, el número y los tipos del primer y último carácter son los mismos [checkLetters()] .
   Por ejemplo, la cadena "ab ba" se puede resolver y contiene primeras letras = {a=1, b=1}, últimas letras = {a=1, b=1}, y la cadena "ab ba bc" es indecidible y contiene primeras letras = {a=
   1, b=2 }, últimas letras = {a=1, b=1, c=1 }.
   
3. Todas las palabras en W están conectadas entre sí [checkConnectivity()] . Por ejemplo, la palabra "ab" proporciona la conexión [a,b], en la secuencia "ab bc cd da" los símbolos conectados [a,b,c,d], ambas secuencias son decidibles. Pero la secuencia "ab bc ca fg gf" no tiene solución y contiene 2 bloques desconectados: {[a,b,c] y [f,g]}. Verifiqué la conectividad usando List<set<character>> de la siguiente manera:
   • 3.1. Tomamos cualquier palabra, comprobamos si su primer/último carácter está contenido en algún Conjunto<carácter>
   • 3.2. Si ninguno de los Set<character> contiene su primera o última letra, cree un nuevo Set<character> con ellas
   • 3.3. Si solo 1 conjunto<carácter> contiene su primera/última letra, agregue otra letra a este conjunto
   • 3.4. Si 1 conjunto contiene la primera letra y el segundo la última, combinamos estos conjuntos
   • 3.5. Repetir para todas las palabras.
   • 3.6. Si al final List<set<character>> contiene solo 1 conjunto, la secuencia está conectada , si hay más de 1, entonces no está conectada y no se puede resolver.

<h3>2.3. Buscar la secuencia final [generateResultLists()]</h3>Para buscar, tuvimos que crear una clase adicional CycleList, que contiene una Lista<palabra> que satisface las condiciones de la tarea, así como un Conjunto<carácter>, que contiene muchos caracteres de la Lista<palabras>. La "característica" principal de esta clase es su capacidad de reorganizarse para que la Lista comience (y termine) con cualquier letra necesaria incluida en el Conjunto<carácter>. Por ejemplo, (regroup(b)) "ab bc ca" -> "bc ca ab". Esto le permite fusionar fácilmente 2 de esas hojas que tienen una intersección de símbolos; basta con reagrupar ambas por el símbolo de intersección y puede agregar una hoja a la otra (el algoritmo descrito anteriormente se implementa con bastante facilidad).

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 conclusiónMe gustó mucho el problema, tuve que devanarme los sesos desde el punto de vista del algoritmo, pero no me arrepiento en absoluto. Mientras combinaba el código resultante, comencé a comprender mejor cómo trabajar con expresiones y colecciones lambda en Java. El código descrito funciona bastante rápido: en mi PC, que ya no es joven, se clasifica una serie de 30.000 palabras aleatorias en aproximadamente 1 segundo. Además de la solución descrita, el código en Github también contiene:

1. Generador de secuencia aleatoria
2. La clase SequenceAlgorithm, que implementa el algoritmo de la sección (1.2)
3. Varias secuencias para probar, por ejemplo mi implementación de SequenceAlgorithm no encuentra solución para esta secuencia (ni hacia adelante ni hacia atrás): 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