Tarefa de cadeia de palavras

Ao fazer o curso Java.Multithreading, fiquei muito interessado na tarefa de compor uma cadeia de palavras: https://javarush.com/tasks/com.javarush.task.task22.task2209 . A tarefa em si: dada uma cadeia de palavras, é necessário ordená-las de tal forma que para cada par de palavras a última letra da primeira palavra coincida com a primeira letra da palavra seguinte. Naturalmente, a cadeia final deve incluir todas as palavras da cadeia original uma vez. Por exemplo, "Kiev Nova York Amsterdã Viena Melbourne" -> "Amsterdã Melbourne Nova York Kiev Viena" ou "ab ac bc" -> "ab bc ca". O problema me interessou do ponto de vista da combinatória e da busca de uma solução. <h2>1. Algoritmo</h2><h3>1.1. Força bruta</h3>O algoritmo mais simples que vem à mente é pesquisar todas as combinações possíveis até encontrar a desejada. A principal desvantagem é um aumento acentuado e acelerado no número de combinações - o número de combinações para n palavras será igual ao fatorial e a complexidade do algoritmo é O(n!). Para 3 palavras, obtém-se o seguinte conjunto - 6 combinações: Para 4 palavras: a Wikipedia sugere que para 10 palavras haverá 3,2 milhões de combinações, e para 100 palavras - ~10^158 combinações. Passar por tantas combinações parece um tanto... difícil... <h3>1.2. Incremento</h3>Portanto, precisamos de algum outro algoritmo, e não apenas de enumeração, por exemplo, junção sequencial: (1) Pegue a primeira palavra, (2) Pegue a próxima e tente juntá-la (à esquerda ou à direita ) para o primeiro. Se funcionar, repita para todas as palavras restantes. (3) Se a lista inicial estiver vazia, encontramos a sequência; se não estiver vazia, falha, vá para (4) (4) Tomamos como palavra inicial não a primeira, mas a segunda, etc. Se não me engano, a complexidade desse algoritmo é O(n^2), que é muito menor que o primeiro. O problema é que pode haver sequências (bastante longas) para as quais começar com qualquer caractere não leva a uma solução - a linha fica em loop e os caracteres restantes não podem ser anexados. Em princípio, outras opções são possíveis - se não funcionar, você pode seguir na ordem inversa (inverter a linha e começar de novo) ou misturar as palavras aleatoriamente, etc. Isso é semelhante a jogar dedais - se não der certo, tentamos misturar os cubos na caixa até obter a sequência desejada. Quanto tempo levará e se funcionará não está claro. <h3>1.3. Sequências cíclicas Este algoritmo é baseado em uma ideia simples: se tivermos 2 sequências que satisfaçam as condições do problema, elas podem ser combinadas em uma se contiverem caracteres que se cruzam. E o algoritmo será assim: (1) Divida a sequência original em x sequências cíclicas mínimas que satisfaçam as condições do problema (2) Combine as sequências cíclicas em uma sequência final que satisfaça as condições do problema. É importante notar que palavras contendo a mesma primeira e última letras, neste caso, podem ser consideradas sequências cíclicas mínimas. E podem ser anexados a outras palavras no estágio (1) ou deixados no estágio (2). <h2>2. Implementação</h2>O código está postado no github , além disso, se necessário, mencionarei [funções] que implementam a tarefa descrita. <h3>2.1. Tijolo elementar</h3>Durante a implementação, você terá que se referir muitas vezes à primeira e à última letras de uma palavra, portanto, uma classe contendo, além da própria palavra, também sua primeira e última letras foi usada como tijolo elementar :

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. Verificando a sequência original</h3>Antes de iniciar o algoritmo de busca principal, você deve ter certeza de que o problema é, em princípio, solucionável. Eu implementei isso usando as seguintes verificações (doravante neste parágrafo, S é a string de origem, W é a matriz do Word criada com base nela):

1. S não é nulo, comprimento S > 0 (bem, isso é óbvio)
2. Em W, o número e os tipos do primeiro e do último caracteres são iguais [checkLetters()] .
   Por exemplo, a string "ab ba" pode ser resolvida e contém firstLetters = {a=1, b=1}, lastLetters = {a=1, b=1}, e a string "ab ba bc" é indecidível e contém firstLetters = {a=
   1 , b=2 }, últimas letras = {a=1, b=1, c=1 }.
   
3. Todas as palavras em W estão conectadas entre si [checkConnectivity()] . Por exemplo, a palavra "ab" fornece a conexão [a,b], na sequência "ab bc cd da" os símbolos conectados [a,b,c,d], ambas as sequências são decidíveis. Mas a sequência "ab bc ca fg gf" é insolúvel e contém 2 blocos desconectados: {[a,b,c] e [f,g]}. Verifiquei a conectividade usando List<set<character>> da seguinte forma:
   • 3.1. Pegamos qualquer palavra, verificamos se seu primeiro/último caractere está contido em qualquer Set<character>
   • 3.2. Se nenhum Set<character> contiver sua primeira ou última letra - crie um novo Set<character> com eles
   • 3.3. Se apenas 1 Set<character> contiver sua primeira/última letra - adicione outra letra a este Set
   • 3.4. Se 1 conjunto contém a primeira letra e o segundo a última, combinamos esses conjuntos
   • 3.5. Repita para todas as palavras
   • 3.6. Se no final List<set<character>> contiver apenas 1 conjunto, a sequência será conectada ; se houver mais de 1, ela não estará conectada e não poderá ser resolvida.

<h3>2.3. Procure a sequência final [generateResultLists()]</h3>Para pesquisar, tivemos que criar uma classe adicional CycleList, que contém uma List<palavra> que satisfaça as condições da tarefa, bem como um Set<character>, que contém muitos caracteres da Lista<palavras>. A principal "característica" desta classe é sua capacidade de reorganizar para que a Lista comece (e termine) com qualquer letra necessária incluída no Set<caractere>. Por exemplo, (regrupo(b)) "ab bc ca" -> "bc ca ab". Isso permite mesclar facilmente 2 dessas folhas que possuem uma interseção de símbolos - basta reagrupar ambas pelo símbolo de interseção e você pode adicionar uma folha à outra (o algoritmo descrito acima é implementado com bastante facilidade).

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. Concluindo, gostei muito do problema, tive que quebrar a cabeça do ponto de vista do algoritmo, mas não me arrependo nem um pouco. Ao analisar o código resultante, comecei a entender melhor como trabalhar com expressões e coleções lambda em Java. O código descrito funciona muito rapidamente: no meu PC, que já não é mais jovem, uma matriz de 30.000 palavras aleatórias é classificada em cerca de 1 segundo. Além da solução descrita, o código no Github também contém:

1. Gerador de sequência aleatória
2. A classe SequenceAlgorithm, que implementa o algoritmo da seção (1.2)
3. Várias sequências para testar, por exemplo minha implementação do SequenceAlgorithm não encontra solução para esta sequência (nem para frente nem para trá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