Compito di catena di parole

Durante il corso Java.Multithreading, ero molto interessato al compito di comporre una catena di parole: https://javarush.com/tasks/com.javarush.task.task22.task2209 . Il compito in sé: data una catena di parole, è necessario ordinarle in modo tale che per ogni coppia di parole l'ultima lettera della prima parola coincida con la prima lettera di quella successiva. Naturalmente la catena finale deve contenere tutte le parole della catena originale una sola volta. Ad esempio: "Kiev New York Amsterdam Vienna Melbourne" -> "Amsterdam Melbourne New York Kiev Vienna" oppure "ab ac bc" -> "ab bc ca". Il problema mi interessava dal punto di vista della combinatoria e della ricerca di una soluzione. <h2>1. Algoritmo</h2><h3>1.1. Forza bruta</h3>L'algoritmo più semplice che mi viene in mente è cercare tra tutte le combinazioni possibili finché non viene trovata quella desiderata. Lo svantaggio principale è un aumento netto e accelerato del numero di combinazioni: il numero di combinazioni per n parole sarà uguale al fattoriale e la complessità dell'algoritmo è O(n!). Per 3 parole, si ottiene il seguente insieme: 6 combinazioni: Per 4 parole: Wikipedia suggerisce che per 10 parole ci saranno 3,2 milioni di combinazioni e per 100 parole - ~10^158 combinazioni. Passare attraverso un tale numero di combinazioni sembra un po'... difficile... <h3>1.2. Incremento</h3>Quindi, abbiamo bisogno di qualche altro algoritmo, e non solo dell'enumerazione, ad esempio l'unione sequenziale: (1) Prendi la prima parola, (2) Prendi quella successiva e prova a unirla (a sinistra o a destra ) al primo. Se funziona, ripeti per tutte le parole rimanenti. (3) Se la lista iniziale è vuota, abbiamo trovato la sequenza; se non è vuota, fallimento, vai a (4) (4) Prendiamo come parola iniziale non la prima, ma la seconda, ecc. Se non sbaglio la complessità di questo algoritmo è O(n^2), che è molto inferiore al primo. Il problema è che possono esserci sequenze (piuttosto lunghe) per le quali iniziare con un carattere qualsiasi non porta a una soluzione: la riga si ripete in loop e i caratteri rimanenti non possono essere aggiunti. In linea di principio sono possibili ulteriori opzioni: se non funziona, puoi procedere nell'ordine inverso (invertire la riga e ricominciare da capo), oppure mescolare le parole in modo casuale, ecc. È simile al gioco dei ditali: se non funziona, proviamo a mescolare i cubi nella scatola finché non otteniamo la sequenza desiderata. Quanto tempo ci vorrà e se funzionerà non è chiaro. <h3>1.3. Sequenze cicliche</h3>Questo algoritmo si basa su un'idea semplice: se abbiamo 2 sequenze che soddisfano le condizioni del problema, possono essere combinate in una sola se contengono caratteri che si intersecano. E l'algoritmo sarà così: (1) Dividere la sequenza originale in x sequenze cicliche minime che soddisfano le condizioni del problema (2) Combina le sequenze cicliche in una sequenza finale che soddisfa le condizioni del problema. Vale la pena notare che le parole contenenti la stessa prima e ultima lettera in questo caso possono essere considerate come sequenze cicliche minime. E possono essere attaccati ad altre parole nella fase (1) o lasciati per la fase (2). <h2>2. Implementazione</h2>Il codice è pubblicato su github , inoltre, se necessario, menzionerò [funzioni] che implementano l'attività descritta. <h3>2.1. Mattone elementare</h3>Durante l'implementazione si dovrà fare molto spesso riferimento alla prima e all'ultima lettera di una parola, quindi è stata utilizzata come mattone elementare una classe contenente, oltre alla parola stessa, anche la sua prima e ultima lettera :

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. Controllo della sequenza originale</h3>Prima di avviare l'algoritmo di ricerca principale, dovresti assicurarti che il problema sia, in linea di principio, risolvibile. L'ho implementato utilizzando i seguenti controlli (di seguito in questo paragrafo, S è la stringa sorgente, W è l'array Word creato in base ad essa):

1. S non è nullo, lunghezza S > 0 (beh, è ​​ovvio)
2. In W, il numero e i tipi del primo e dell'ultimo carattere sono gli stessi [checkLetters()] .
   Ad esempio, la stringa "ab ba" è risolvibile e contiene firstLetters = {a=1, b=1}, lastLetters = {a=1, b=1} e la stringa "ab ba bc" è indecidibile e contiene firstLetters = {a=
   1 , b=2 }, ultimeLettere = {a=1, b=1, c=1 }.
   
3. Tutte le parole in W sono collegate tra loro [checkConnectivity()] . Ad esempio, la parola "ab" fornisce la connessione [a,b], nella sequenza "ab bc cd da" i simboli connessi [a,b,c,d], entrambe queste sequenze sono decidibili. Ma la sequenza "ab bc ca fg gf" è irrisolvibile e contiene 2 blocchi sconnessi: {[a,b,c] e [f,g]}. Ho controllato la connettività utilizzando List<set<character>> come segue:
   • 3.1. Prendiamo qualsiasi parola, controlliamo se il suo primo/ultimo carattere è contenuto in qualsiasi Set<carattere>
   • 3.2. Se nessuno dei Set<carattere> contiene la sua prima o ultima lettera, crea un nuovo Set<carattere> con essi
   • 3.3. Se solo 1 Set<carattere> contiene la sua prima/ultima lettera, aggiungi un'altra lettera a questo Set
   • 3.4. Se 1 set contiene la prima lettera e la seconda l'ultima, combiniamo questi set
   • 3.5. Ripeti per tutte le parole
   • 3.6. Se alla fine List<set<carattere>> contiene solo 1 set, la sequenza è connessa , se più di 1, allora non è connessa e non può essere risolta.

<h3>2.3. Cerca la sequenza finale [generateResultLists()]</h3>Per effettuare la ricerca, abbiamo dovuto creare una classe aggiuntiva CycleList, che contiene un List<word> che soddisfa le condizioni dell'attività, nonché un Set<character>, che contiene molti caratteri dall'elenco<parole>. La "caratteristica" principale di questa classe è la sua capacità di riorganizzarsi in modo che List inizi (e finisca) con qualsiasi lettera necessaria inclusa nel Set<carattere>. Ad esempio, (regroup(b)) "ab bc ca" -> "bc ca ab". Ciò ti consente di unire facilmente 2 fogli che hanno un'intersezione di simboli: è sufficiente raggrupparli entrambi in base al simbolo di intersezione e puoi aggiungere un foglio all'altro (l'algoritmo sopra descritto è implementato abbastanza facilmente).

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. In conclusione</h2>il problema mi è piaciuto molto, mi sono dovuto scervellare dal punto di vista dell'algoritmo, ma non me ne pento affatto. Analizzando il codice risultante, ho iniziato a comprendere meglio come lavorare con le espressioni e le raccolte lambda in Java. Il codice descritto funziona abbastanza velocemente; sul mio non più giovane PC viene ordinato un array di 30.000 parole casuali in circa 1 secondo. Oltre alla soluzione descritta, il codice su Github contiene anche:

1. Generatore di sequenze casuali
2. La classe SequenceAlgorithm, che implementa l'algoritmo della sezione (1.2)
3. Diverse sequenze da testare, ad esempio la mia implementazione di SequenceAlgorithm non trova una soluzione per questa sequenza (né in avanti né all'indietro): 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