Tugas rantai kata

Saat mengikuti kursus Java.Multithreading, saya sangat tertarik dengan tugas menyusun rangkaian kata: https://javarush.com/tasks/com.javarush.task.task22.task2209 . Tugasnya sendiri: mengingat rangkaian kata, perlu diurutkan sedemikian rupa sehingga untuk setiap pasangan kata, huruf terakhir dari kata pertama bertepatan dengan huruf pertama dari kata berikutnya. Tentu saja, rantai terakhir harus mencakup semua kata dari rantai aslinya satu kali. Misalnya, "Kiev New York Amsterdam Vienna Melbourne" -> "Amsterdam Melbourne New York Kiev Vienna" atau "ab ac bc" -> "ab bc ca". Masalahnya menarik minat saya dari sudut pandang kombinatorik dan mencari solusi. <h2>1. Algoritma</h2><h3>1.1. Brute-force</h3>Algoritme paling sederhana yang terlintas dalam pikiran adalah mencari semua kemungkinan kombinasi hingga kombinasi yang diinginkan ditemukan. Kerugian utama adalah peningkatan jumlah kombinasi yang tajam dan cepat - jumlah kombinasi untuk n kata akan sama dengan faktorial dan kompleksitas algoritme adalah O(n!). Untuk 3 kata, diperoleh himpunan berikut - 6 kombinasi: Untuk 4 kata: Wikipedia menyarankan bahwa untuk 10 kata akan ada 3,2 juta kombinasi, dan untuk 100 kata - ~10^158 kombinasi. Melewati sejumlah kombinasi sepertinya agak... sulit... <h3>1.2. Kenaikan</h3>Jadi, kita memerlukan algoritma lain, dan bukan hanya enumerasi, misalnya penggabungan berurutan: (1) Ambil kata pertama, (2) Ambil kata berikutnya dan coba gabungkan (di kiri atau kanan ) ke yang pertama. Jika berhasil, ulangi untuk semua kata yang tersisa. (3) Jika daftar awal kosong, kita telah menemukan urutannya; jika tidak kosong, gagal, lanjutkan ke (4) (4) Kita ambil sebagai kata awal bukan yang pertama, tetapi yang kedua, dan seterusnya. Kalau tidak salah, kompleksitas algoritma ini adalah O(n^2), jauh lebih kecil dari algoritma pertama. Masalahnya adalah mungkin ada urutan (cukup panjang) yang memulai dengan karakter apa pun tidak menghasilkan solusi - baris menjadi berulang dan karakter lainnya tidak dapat ditambahkan. Pada prinsipnya, opsi lebih lanjut dimungkinkan - jika tidak berhasil, Anda dapat melakukannya dalam urutan terbalik (membalikkan baris dan memulai dari awal), atau mencampur kata secara acak, dll. Ini mirip dengan bermain bidal - jika tidak berhasil, kami mencoba mencampur kubus di dalam kotak sampai kami mendapatkan urutan yang diinginkan. Berapa lama waktu yang dibutuhkan dan apakah akan berhasil masih belum jelas. <h3>1.3. Urutan siklik</h3>Algoritme ini didasarkan pada ide sederhana: jika kita memiliki 2 urutan yang memenuhi kondisi masalah, maka urutan tersebut dapat digabungkan menjadi satu jika mengandung karakter yang berpotongan. Dan algoritmanya akan seperti ini: (1) Membagi barisan asli menjadi x barisan siklik minimal yang memenuhi kondisi masalah (2) Menggabungkan barisan siklik menjadi satu barisan akhir yang memenuhi kondisi masalah. Perlu dicatat bahwa kata-kata yang mengandung huruf pertama dan terakhir yang sama dalam hal ini dapat dianggap sebagai barisan siklik minimal. Dan kata-kata tersebut dapat dilampirkan ke kata lain pada tahap (1) atau dibiarkan ke tahap (2). <h2>2. Implementasi</h2>Kode diposting di github , selanjutnya, jika perlu, saya akan menyebutkan [fungsi] yang mengimplementasikan tugas yang dijelaskan. <h3>2.1. Elementary brick</h3>Selama implementasi, Anda harus sering mengacu pada huruf pertama dan terakhir dari sebuah kata, jadi kelas yang berisi, selain kata itu sendiri, juga huruf pertama dan terakhirnya digunakan sebagai elemen brick :

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. Memeriksa urutan asli</h3>Sebelum memulai algoritma pencarian utama, Anda harus memastikan bahwa masalahnya, pada prinsipnya, dapat dipecahkan. Saya menerapkan ini menggunakan pemeriksaan berikut (selanjutnya dalam paragraf ini, S adalah string sumber, W adalah array Word yang dibuat berdasarkan itu):

1. S bukan nol, panjangnya S > 0 (ya, itu sudah jelas)
2. Di W, jumlah dan tipe karakter pertama dan terakhir adalah sama [checkLetters()] .
   Misalnya, string "ab ba" dapat dipecahkan dan berisi FirstLetters = {a=1, b=1}, lastLetters = {a=1, b=1}, Dan string "ab ba bc" tidak dapat diputuskan dan berisi FirstLetters = {a=
   1 , b=2 },Huruf terakhir = {a=1, b=1, c=1 }.
   
3. Semua kata di W terhubung satu sama lain [checkConnectivity()] . Misalnya, kata "ab" memberikan keterhubungan [a,b], pada barisan "ab bc cd da" simbol-simbol yang terhubung [a,b,c,d], kedua barisan ini dapat ditentukan. Namun barisan "ab bc ca fg gf" tidak dapat diselesaikan dan berisi 2 blok yang tidak terhubung: {[a,b,c] dan [f,g]}. Saya memeriksa konektivitas menggunakan List<set<character>> sebagai berikut:
   • 3.1. Kami mengambil kata apa pun, memeriksa apakah karakter pertama/terakhirnya terkandung dalam Set<karakter> apa pun
   • 3.2. Jika tidak ada Set<karakter> yang berisi huruf pertama atau terakhir - buat Set<karakter> baru dengan huruf tersebut
   • 3.3. Jika hanya 1 Set<character> yang berisi huruf pertama/terakhir - tambahkan huruf lain ke Set ini
   • 3.4. Jika 1 set berisi huruf pertama, dan yang kedua berisi huruf terakhir, kami menggabungkan set ini
   • 3.5. Ulangi untuk semua kata
   • 3.6. Jika pada akhirnya List<set<character>> hanya berisi 1 himpunan maka rangkaiannya connect , jika lebih dari 1 maka tidak nyambung dan tidak dapat diselesaikan.

<h3>2.3. Cari urutan terakhir [generateResultLists()]</h3>Untuk mencari, kita harus membuat kelas CycleList tambahan, yang berisi Daftar<kata> yang memenuhi kondisi tugas, serta Set<karakter>, yang berisi banyak karakter dari Daftar<kata>. "Fitur" utama kelas ini adalah kemampuannya untuk mengatur ulang sehingga Daftar dimulai (dan diakhiri) dengan huruf apa pun yang diperlukan yang termasuk dalam Set<karakter>. Misalnya, (kelompokkan kembali(b)) "ab bc ca" -> "bc ca ab". Hal ini memungkinkan Anda untuk dengan mudah menggabungkan 2 lembar yang memiliki perpotongan simbol - cukup dengan mengelompokkan kembali keduanya dengan simbol yang berpotongan dan Anda dapat menambahkan satu lembar ke lembar lainnya (algoritme yang dijelaskan di atas diterapkan dengan cukup 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 masalahnya, saya harus memutar otak dari sudut pandang algoritma, tetapi saya tidak menyesalinya sama sekali. Sambil menyisir kode yang dihasilkan, saya mulai lebih memahami bekerja dengan ekspresi dan koleksi lambda di Java. Kode yang dijelaskan bekerja cukup cepat; pada PC saya yang sudah tidak muda lagi, rangkaian 30.000 kata acak diurutkan dalam waktu sekitar 1 detik. Selain solusi yang dijelaskan, kode di Github juga berisi:

1. Generator Urutan Acak
2. Kelas SequenceAlgorithm, yang mengimplementasikan algoritma dari bagian (1.2)
3. Beberapa sequence yang akan diuji, misalnya implementasi SequenceAlgorithm saya tidak menemukan solusi untuk sequence ini (baik maju maupun mundur): 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