Tugas rantai tembung

Nalika njupuk kursus Java.Multithreading, aku banget kasengsem ing tugas nyusun rantai tembung: https://javarush.com/tasks/com.javarush.task.task22.task2209 . Tugas kasebut dhewe: diwenehi rantai tembung, kudu diurutake supaya saben pasangan tembung huruf pungkasan tembung pisanan pas karo huruf pisanan sabanjure. Mesthi wae, ranté pungkasan kudu nyakup kabeh tembung saka ranté asli sapisan. Contone, "Kiev New York Amsterdam Vienna Melbourne" -> "Amsterdam Melbourne New York Kiev Wina" utawa "ab ac bc" -> "ab bc ca". Masalah kasengsem kula saka sudut pandang combinatorics lan nemokake solusi. <h2>1. Algoritma </h2><h3>1.1. Brute-force</h3>Algoritma paling gampang sing dipikirake yaiku nggoleki kabeh kombinasi sing bisa ditindakake nganti sing dikarepake ditemokake. Kerugian utama yaiku tambah akeh kombinasi sing cetha lan nyepetake - jumlah kombinasi kanggo n tembung bakal padha karo faktorial lan kerumitan algoritma yaiku O (n!). Kanggo 3 tembung, set ing ngisor iki dipikolehi - 6 kombinasi: Kanggo 4 tembung: Wikipedia nyaranake manawa kanggo 10 tembung bakal ana 3,2 yuta kombinasi, lan kanggo 100 tembung - ~10^158 kombinasi. Ngliwati kombinasi kaya mengkono katon rada ... angel ... <h3> 1.2. Increment</h3>Dadi, kita butuh sawetara algoritma liyane, lan ora mung enumerasi, contone, gabung urut-urutan: (1) Njupuk tembung pisanan, (2) Njupuk tembung sabanjuré lan nyoba kanggo gabung (ing kiwa utawa tengen). ) kanggo pisanan. Yen bisa, baleni kanggo kabeh tembung sing isih ana. (3) Yen dhaptar dhisikan kosong, kita wis nemokake urutane, yen ora kosong, gagal, pindhah menyang (4) (4) Kita njupuk minangka tembung wiwitan ora pisanan, nanging kaloro, etc. Yen aku ora salah, kerumitan algoritma iki yaiku O (n ^ 2), sing luwih murah tinimbang sing pisanan. Masalahe yaiku bisa ana urutan (cukup dawa) sing diwiwiti karo karakter apa wae ora mimpin menyang solusi - baris kasebut dadi loop lan karakter sing isih ora bisa ditambahake. Ing asas, opsi luwih bisa uga - yen ora bisa, sampeyan bisa pindhah ing urutan mbalikke (mbalikke baris lan miwiti maneh), utawa acak nyampur munggah tembung, etc. Iki padha karo muter thimbles - yen ora bisa, kita nyoba kanggo nyampur kubus ing kothak nganti njaluk urutan sing dikarepake. Suwene suwene lan apa bakal bisa digunakake ora jelas. <h3>1.3. Urutan siklik</h3>Algoritma iki adhedhasar gagasan prasaja: yen kita duwe 2 urutan sing nyukupi kondisi masalah, bisa digabung dadi siji yen ngemot karakter intersecting. Lan algoritma bakal kaya mangkene: (1) Pisah urutan asli dadi x urutan siklik minimal sing nyukupi kondisi masalah (2) Gabungke urutan siklus dadi siji urutan pungkasan sing nyukupi kondisi masalah. Wigati dicathet menawa tembung sing ngemot huruf pisanan lan pungkasan sing padha ing kasus iki bisa dianggep minangka urutan siklik minimal. Lan bisa uga digandhengake karo tembung liya ing tataran (1) utawa ditinggalake kanggo tataran (2). <h2>2. Implementasi</h2>Kode kasebut dikirim ing github , luwih, yen perlu, aku bakal nyebutake [fungsi] sing ngetrapake tugas sing diterangake. <h3>2.1. Bata dhasar</h3>Sajrone implementasine, sampeyan kudu kerep ngrujuk marang huruf pisanan lan pungkasan saka tembung, supaya kelas sing ngemot, saliyane tembung kasebut, uga huruf pisanan lan pungkasan digunakake minangka bata dhasar. :

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. Priksa urutan asli</h3>Sadurunge miwiti algoritma telusuran utama, sampeyan kudu nggawe manawa masalah kasebut, ing prinsip, bisa dipecahake. Aku ngetrapake iki kanthi nggunakake mriksa ing ngisor iki (sabanjuré ing paragraf iki, S minangka string sumber, W minangka susunan Word sing digawe adhedhasar):

1. S ora null, dawa S > 0 (ya, sing jelas)
2. Ing W, nomer lan jinis karakter pisanan lan pungkasan padha [checkLetters ()] .
   Contone, string "ab ba" bisa dipecahake lan ngemot FirstLetters = {a=1, b=1}, lastLetters = {a=1, b=1}, Lan string "ab ba bc" ora bisa ditemtokake lan ngemot FirstLetters. = {a=
   1 , b=2 }, aksara pungkasan = {a=1, b=1, c=1 }.
   
3. Kabeh tembung ing W disambungake kanggo saben liyane [checkConnectivity ()] . Contone, tembung "ab" nyedhiyakake sambungan [a,b], ing urutan "ab bc cd da" simbol sing disambungake [a,b,c,d], loro-lorone urutan kasebut bisa ditemtokake. Nanging urutan "ab bc ca fg gf" ora bisa dipecahake lan ngemot 2 blok sing dicopot: {[a,b,c] lan [f,g]}. Aku mriksa konektivitas nggunakake List<set<character>> kaya ing ngisor iki:
   • 3.1. Kita njupuk tembung apa wae, priksa manawa karakter pisanan / pungkasan ana ing Set<karakter>
   • 3.2. Yen ora ana Set<karakter> sing ngemot aksara pisanan utawa pungkasan - gawe Set<karakter> anyar karo dheweke
   • 3.3. Yen mung 1 Set<karakter> ngemot aksara pisanan/pungkasan - tambahake huruf liyane menyang Set iki
   • 3.4. Yen 1 set ngemot huruf pisanan, lan kaloro pungkasan, kita gabungke set kasebut
   • 3.5. Baleni kanggo kabeh tembung
   • 3.6. Yen ing pungkasan List<set<character>> mung ngemot 1 set, urutane disambungake , yen luwih saka 1, mula ora nyambung lan ora bisa diatasi.

<h3>2.3. Telusuri urutan pungkasan [generateResultLists()]</h3>Kanggo nggoleki, kita kudu nggawe kelas CycleList tambahan, sing ngemot List<word> sing nyukupi kondisi tugas, uga Set<karakter>, sing ngemot akeh karakter saka Daftar<tembung>. "Fitur" utama kelas iki yaiku kemampuan kanggo ngatur maneh supaya Dhaptar diwiwiti (lan diakhiri) kanthi huruf sing dibutuhake kalebu ing Set<karakter>. Contone, (regroup(b)) "ab bc ca" -> "bc ca ab". Iki ngidini sampeyan kanthi gampang nggabungake 2 lembar kasebut sing duwe persimpangan simbol - cukup kanggo nglumpukake loro-lorone kanthi simbol intersecting lan sampeyan bisa nambah siji sheet menyang liyane (algoritma sing diterangake ing ndhuwur gampang ditindakake).

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. Kesimpulane</h2>Aku seneng banget karo masalah kasebut, aku kudu rak otak saka sudut pandang algoritma, nanging aku ora Getun ing kabeh. Nalika nyisir kode sing diasilake, aku wiwit luwih ngerti nggarap ekspresi lan koleksi lambda ing Jawa. Kode sing diterangake bisa dianggo kanthi cepet; ing PC sing ora enom maneh, macem-macem 30,000 tembung acak diurutake sajrone 1 detik. Saliyane solusi sing diterangake, kode ing Github uga ngemot:

1. Generator urutan acak
2. Kelas SequenceAlgorithm, sing ngetrapake algoritma saka bagean (1.2)
3. Sawetara urutan kanggo nyoba, contone, implementasine SequenceAlgorithm ora nemokake solusi kanggo urutan iki (ora maju utawa 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