Tugas rantaian perkataan

Semasa mengikuti kursus Java.Multithreading, saya sangat berminat dengan tugas mengarang rangkaian perkataan: https://javarush.com/tasks/com.javarush.task.task22.task2209 . Tugas itu sendiri: diberikan rantaian perkataan, adalah perlu untuk memerintahkannya sedemikian rupa sehingga untuk setiap pasangan perkataan huruf terakhir perkataan pertama bertepatan dengan huruf pertama yang seterusnya. Sememangnya, rantai terakhir mesti memasukkan semua perkataan rantai asal sekali. Contohnya, "Kiev New York Amsterdam Vienna Melbourne" -> "Amsterdam Melbourne New York Kiev Vienna" atau "ab ac bc" -> "ab bc ca". Masalah itu menarik minat saya dari sudut kombinatorik dan mencari penyelesaian. <h2>1. Algoritma</h2><h3>1.1. Brute-force</h3>Algoritma paling mudah yang terlintas di fikiran ialah mencari melalui semua kombinasi yang mungkin sehingga kombinasi yang dikehendaki ditemui. Kelemahan utama ialah peningkatan mendadak dan mempercepatkan bilangan gabungan - bilangan gabungan untuk n perkataan akan sama dengan faktorial dan kerumitan algoritma ialah O(n!). Untuk 3 perkataan, set berikut diperoleh - 6 gabungan: Untuk 4 perkataan: Wikipedia mencadangkan bahawa untuk 10 perkataan akan ada 3.2 juta gabungan, dan untuk 100 perkataan - ~10^158 gabungan. Menerusi beberapa kombinasi sedemikian kelihatan agak... sukar... <h3>1.2. Kenaikan</h3>Jadi, kita memerlukan beberapa algoritma lain, dan bukan hanya penghitungan, sebagai contoh, penyambungan berurutan: (1) Ambil perkataan pertama, (2) Ambil yang seterusnya dan cuba untuk menyertainya (di sebelah kiri atau kanan ) kepada yang pertama. Jika ia berkesan, ulangi untuk semua perkataan yang tinggal. (3) Jika senarai awal kosong, kami telah menemui urutannya; jika ia tidak kosong, kegagalan, pergi ke (4) (4) Kami mengambil sebagai perkataan awal bukan yang pertama, tetapi yang kedua, dsb. Jika saya tidak silap, kerumitan algoritma ini ialah O(n^2), yang jauh lebih kecil daripada yang pertama. Masalahnya ialah mungkin terdapat urutan (agak panjang) yang bermula dengan mana-mana aksara tidak membawa kepada penyelesaian - garisan menjadi bergelung dan aksara yang tinggal tidak boleh ditambah. Pada dasarnya, pilihan lanjut adalah mungkin - jika ia tidak berfungsi, anda boleh pergi dalam susunan terbalik (terbalikkan baris dan mulakan semula), atau mencampurkan perkataan secara rawak, dsb. Ini serupa dengan bermain bidal - jika tidak berjaya, kami cuba mencampurkan kiub di dalam kotak sehingga kami mendapat urutan yang diingini. Berapa lama ia akan diambil dan sama ada ia akan berfungsi tidak jelas. <h3>1.3. Jujukan kitaran</h3>Algoritma ini berdasarkan idea mudah: jika kita mempunyai 2 jujukan yang memenuhi syarat masalah, ia boleh digabungkan menjadi satu jika ia mengandungi aksara bersilang. Dan algoritmanya akan menjadi seperti ini: (1) Pisahkan urutan asal kepada x jujukan kitaran minimum yang memenuhi syarat masalah (2) Gabungkan jujukan kitaran menjadi satu jujukan akhir yang memenuhi syarat masalah. Perlu diingat bahawa perkataan yang mengandungi huruf pertama dan terakhir yang sama dalam kes ini boleh dianggap sebagai urutan kitaran minimum. Dan mereka boleh sama ada dilampirkan pada perkataan lain pada peringkat (1) atau dibiarkan untuk peringkat (2). <h2>2. Implementation</h2>Kod ini disiarkan pada github , selanjutnya, jika perlu, saya akan menyebut [functions] yang melaksanakan tugas yang diterangkan. <h3>2.1. Bata asas</h3>Semasa pelaksanaan, anda perlu selalu merujuk kepada huruf pertama dan terakhir perkataan, jadi kelas yang mengandungi, sebagai tambahan kepada perkataan itu sendiri, juga huruf pertama dan terakhirnya digunakan sebagai bata asas :

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. Menyemak urutan asal</h3>Sebelum memulakan algoritma carian utama, anda harus memastikan bahawa masalah itu, pada dasarnya, boleh diselesaikan. Saya melaksanakan ini menggunakan semakan berikut (selepas ini dalam perenggan ini, S ialah rentetan sumber, W ialah tatasusunan Word yang dibuat berdasarkannya):

1. S bukan nol, panjang S > 0 (nah, itu jelas)
2. Dalam W, bilangan dan jenis aksara pertama dan terakhir adalah sama [checkLetters()] .
   Sebagai contoh, rentetan "ab ba" boleh diselesaikan dan mengandungi Huruf pertama = {a=1, b=1}, Huruf terakhir = {a=1, b=1}, Dan rentetan "ab ba bc" tidak dapat ditentukan dan mengandungi Huruf pertama = {a=
   1 , b=2 }, Huruf terakhir = {a=1, b=1, c=1 }.
   
3. Semua perkataan dalam W disambungkan antara satu sama lain [checkConnectivity()] . Sebagai contoh, perkataan "ab" memberikan keterkaitan [a,b], dalam urutan "ab bc cd da" simbol bersambung [a,b,c,d], kedua-dua jujukan ini boleh ditentukan. Tetapi jujukan "ab bc ca fg gf" tidak boleh diselesaikan dan mengandungi 2 blok terputus: {[a,b,c] dan [f,g]}. Saya menyemak kesambungan menggunakan List<set<character>> seperti berikut:
   • 3.1. Kami mengambil sebarang perkataan, semak sama ada aksara pertama/terakhirnya terkandung dalam mana-mana Set<character>
   • 3.2. Jika tiada Set<character> mengandungi huruf pertama atau terakhirnya - buat Set<character> baharu dengannya
   • 3.3. Jika hanya 1 Set<character> mengandungi huruf pertama/terakhirnya - tambah satu lagi huruf pada Set ini
   • 3.4. Jika 1 set mengandungi huruf pertama, dan yang kedua yang terakhir, kami menggabungkan set ini
   • 3.5. Ulang untuk semua perkataan
   • 3.6. Jika pada akhirnya Senarai<set<character>> mengandungi hanya 1 set, urutan disambungkan , jika lebih daripada 1, maka ia tidak disambungkan dan tidak boleh diselesaikan.

<h3>2.3. Cari urutan akhir [generateResultLists()]</h3>Untuk mencari, kami perlu mencipta kelas CycleList tambahan, yang mengandungi Senarai<word> yang memenuhi syarat tugasan, serta Set<character>, yang mengandungi banyak aksara daripada Senarai<perkataan>. "Ciri" utama kelas ini ialah keupayaannya untuk menyusun semula supaya Senarai bermula (dan berakhir) dengan mana-mana huruf yang diperlukan termasuk dalam Set<character>. Contohnya, (kumpulan semula(b)) "ab bc ca" -> "bc ca ab". Ini membolehkan anda dengan mudah menggabungkan 2 helaian sedemikian yang mempunyai persilangan simbol - cukup untuk mengumpulkan semula kedua-duanya dengan simbol bersilang dan anda boleh menambah satu helaian kepada yang lain (algoritma yang diterangkan di atas dilaksanakan dengan mudah).

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. Kesimpulannya</h2>Saya sangat menyukai masalah itu, saya terpaksa memerah otak saya dari sudut pandangan algoritma, tetapi saya tidak menyesal sama sekali. Semasa menyisir kod yang terhasil, saya mula memahami dengan lebih baik bekerja dengan ungkapan dan koleksi lambda di Jawa. Kod yang diterangkan berfungsi dengan cepat; pada PC saya yang tidak lagi muda, susunan 30,000 perkataan rawak diisih dalam kira-kira 1 saat. Sebagai tambahan kepada penyelesaian yang diterangkan, kod pada Github juga mengandungi:

1. Penjana Jujukan Rawak
2. Kelas SequenceAlgorithm, yang melaksanakan algoritma dari bahagian (1.2)
3. Beberapa urutan untuk diuji, contohnya pelaksanaan SequenceAlgorithm saya tidak menemui penyelesaian untuk jujukan ini (tidak ke hadapan atau ke belakang): 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