Chain of words task

Habang kumukuha ng kursong Java.Multithreading, labis akong interesado sa gawain ng pagbuo ng isang hanay ng mga salita: https://javarush.com/tasks/com.javarush.task.task22.task2209 . Ang gawain mismo: binigyan ng isang kadena ng mga salita, kinakailangang i-order ang mga ito sa paraang para sa bawat pares ng mga salita ang huling titik ng unang salita ay tumutugma sa unang titik ng susunod. Naturally, ang huling kadena ay dapat isama ang lahat ng mga salita ng orihinal na kadena nang isang beses. Halimbawa, "Kiev New York Amsterdam Vienna Melbourne" -> "Amsterdam Melbourne New York Kiev Vienna" o "ab ac bc" -> "ab bc ca". Ang problema ay interesado sa akin mula sa punto ng view ng combinatorics at paghahanap ng solusyon. <h2>1. Algorithm</h2><h3>1.1. Brute-force</h3>Ang pinakasimpleng algorithm na nasa isip ay ang paghahanap sa lahat ng posibleng kumbinasyon hanggang sa matagpuan ang ninanais. Ang pangunahing kawalan ay isang matalim at mabilis na pagtaas sa bilang ng mga kumbinasyon - ang bilang ng mga kumbinasyon para sa n mga salita ay magiging katumbas ng factorial at ang pagiging kumplikado ng algorithm ay O(n!). Para sa 3 salita, makukuha ang sumusunod na hanay - 6 na kumbinasyon: Para sa 4 na salita: Iminumungkahi ng Wikipedia na para sa 10 salita ay magkakaroon ng 3.2 milyong kumbinasyon, at para sa 100 salita - ~10^158 na kumbinasyon. Ang pagdaan sa gayong bilang ng mga kumbinasyon ay mukhang medyo... mahirap... <h3>1.2. Increment</h3>Kaya, kailangan namin ng ilang iba pang algorithm, at hindi lamang enumeration, halimbawa, sequential joining: (1) Kunin ang unang salita, (2) Kunin ang susunod at subukang sumali dito (sa kaliwa o kanan ) sa una. Kung ito ay gumagana, ulitin para sa lahat ng natitirang mga salita. (3) Kung ang unang listahan ay walang laman, nakita namin ang pagkakasunud-sunod; kung ito ay walang laman, kabiguan, pumunta sa (4) (4) Kinukuha namin bilang paunang salita hindi ang una, ngunit ang pangalawa, atbp. Kung hindi ako nagkakamali, ang pagiging kumplikado ng algorithm na ito ay O(n^2), na mas mababa kaysa sa una. Ang problema ay maaaring mayroong mga pagkakasunud-sunod (medyo mahaba) kung saan nagsisimula sa anumang karakter ay hindi humahantong sa isang solusyon - ang linya ay nagiging loop at ang natitirang mga character ay hindi maaaring idugtong. Sa prinsipyo, posible ang karagdagang mga pagpipilian - kung hindi ito gumana, maaari kang pumunta sa reverse order (baligtarin ang linya at magsimula muli), o random na paghaluin ang mga salita, atbp. Ito ay katulad ng paglalaro ng thimbles - kung hindi ito gagana, susubukan naming paghaluin ang mga cube sa kahon hanggang makuha namin ang nais na pagkakasunud-sunod. Gaano ito katagal at kung gagana ito ay hindi malinaw. <h3>1.3. Mga paikot na pagkakasunud-sunod</h3>Ang algorithm na ito ay batay sa isang simpleng ideya: kung mayroon tayong 2 pagkakasunud-sunod na nakakatugon sa mga kondisyon ng problema, maaari silang pagsamahin sa isa kung naglalaman ang mga ito ng mga intersecting na character. At ang algorithm ay magiging ganito: (1) Hatiin ang orihinal na sequence sa x minimal cyclic sequence na nakakatugon sa mga kondisyon ng problema (2) Pagsamahin ang cyclic sequence sa isang huling sequence na nakakatugon sa mga kondisyon ng problema. Kapansin-pansin na ang mga salitang naglalaman ng parehong una at huling mga titik sa kasong ito ay maaaring ituring na minimal na cyclic sequence. At maaari silang ilakip sa ibang mga salita sa yugto (1) o iwan para sa yugto (2). <h2>2. Pagpapatupad</h2>Ang code ay nai-post sa github , higit pa, kung kinakailangan, babanggitin ko ang [mga function] na nagpapatupad ng inilarawang gawain. <h3>2.1. Elementary brick</h3>Sa panahon ng pagpapatupad, kailangan mong madalas na sumangguni sa una at huling mga titik ng isang salita, kaya isang klase na naglalaman, bilang karagdagan sa mismong salita, pati na rin ang una at huling mga titik nito ay ginamit bilang elementarya 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. Sinusuri ang orihinal na pagkakasunud-sunod</h3>Bago simulan ang pangunahing algorithm sa paghahanap, dapat mong tiyakin na ang problema ay, sa prinsipyo, nalulusaw. Ipinatupad ko ito gamit ang mga sumusunod na tseke (simula dito sa talatang ito, S ang source string, W ang Word array na nilikha batay dito):

1. S ay hindi null, haba S > 0 (well, halata iyon)
2. Sa W, ang bilang at mga uri ng una at huling mga character ay pareho [checkLetters()] .
   Halimbawa, ang string na "ab ba" ay nalulusaw at naglalaman ng mga firstLetters = {a=1, b=1}, lastLetters = {a=1, b=1}, At ang string na "ab ba bc" ay undecidable at naglalaman ng firstLetters = {a=
   1 , b=2 }, lastLetters = {a=1, b=1, c=1 }.
   
3. Ang lahat ng salita sa W ay konektado sa isa't isa [checkConnectivity()] . Halimbawa, ang salitang "ab" ay nagbibigay ng pagkakakonekta [a,b], sa sequence na "ab bc cd da" ang mga konektadong simbolo [a,b,c,d], pareho sa mga sequence na ito ay mapagpasyahan. Ngunit ang sequence na "ab bc ca fg gf" ay hindi malulutas at naglalaman ng 2 disconnected block: {[a,b,c] at [f,g]}. Sinuri ko ang pagkakakonekta gamit ang List<set<character>> gaya ng sumusunod:
   • 3.1. Kumuha kami ng anumang salita, tingnan kung ang una/huling mga character nito ay nakapaloob sa anumang Set<character>
   • 3.2. Kung wala sa Set<character> ang naglalaman ng una o huling titik nito - gumawa ng bagong Set<character> kasama nila
   • 3.3. Kung 1 Set<character> lang ang naglalaman ng una/huling titik nito - magdagdag ng isa pang letra sa Set na ito
   • 3.4. Kung ang 1 set ay naglalaman ng unang titik, at ang pangalawa ang huli, pinagsama namin ang mga set na ito
   • 3.5. Ulitin para sa lahat ng mga salita
   • 3.6. Kung sa dulo ang List<set<character>> ay naglalaman lamang ng 1 set, ang sequence ay konektado , kung higit sa 1, hindi ito konektado at hindi malulutas.

<h3>2.3. Hanapin ang huling sequence [generateResultLists()]</h3>Upang maghanap, kailangan naming lumikha ng karagdagang klase na CycleList, na naglalaman ng Listahan<word> na tumutugon sa mga kundisyon ng gawain, pati na rin ang Set<character>, na naglalaman ng maraming character mula sa Listahan<mga salita>. Ang pangunahing "tampok" ng klase na ito ay ang kakayahang muling ayusin upang ang Listahan ay magsimula (at magtapos) sa anumang kinakailangang titik na kasama sa Set<character>. Halimbawa, (regroup(b)) "ab bc ca" -> "bc ca ab". Pinapayagan ka nitong madaling pagsamahin ang 2 ganoong mga sheet na may intersection ng mga simbolo - sapat na upang muling pagsamahin ang pareho ng mga ito sa pamamagitan ng intersecting na simbolo at maaari kang magdagdag ng isang sheet sa isa pa (ang algorithm na inilarawan sa itaas ay ipinatupad nang madali).

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. Sa konklusyon</h2>Talagang nagustuhan ko ang problema, kailangan kong i-rack ang aking utak mula sa punto ng view ng algorithm, ngunit hindi ko ito pinagsisisihan. Habang sinusuklay ang resultang code, nagsimula akong mas maunawaan ang pagtatrabaho sa mga expression at koleksyon ng lambda sa Java. Ang inilarawang code ay mabilis na gumagana; sa aking hindi na batang PC, isang hanay ng 30,000 random na salita ay pinagsunod-sunod sa halos 1 segundo. Bilang karagdagan sa inilarawan na solusyon, ang code sa Github ay naglalaman din ng:

1. Random Sequence Generator
2. Ang SequenceAlgorithm class, na nagpapatupad ng algorithm mula sa seksyon (1.2)
3. Maraming mga sequence na susuriin, halimbawa ang aking pagpapatupad ng SequenceAlgorithm ay hindi nakakahanap ng solusyon para sa sequence na ito (ni forward o backward): 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