ภารกิจห่วงโซ่คำ

ในขณะที่เรียนหลักสูตร Java.Multithreading ฉันสนใจงานเขียนห่วงโซ่คำมาก: https://javarush.com/tasks/com.javarush.task.task22.task2209 ภารกิจ: เมื่อพิจารณาจากกลุ่มคำจำเป็นต้องเรียงลำดับในลักษณะที่สำหรับแต่ละคู่ของคำตัวอักษรสุดท้ายของคำแรกจะตรงกับตัวอักษรตัวแรกของคำถัดไป โดยปกติแล้วห่วงโซ่สุดท้ายจะต้องมีคำทั้งหมดของห่วงโซ่เดิมเพียงครั้งเดียว ตัวอย่างเช่น "เคียฟ นิวยอร์ก อัมสเตอร์ดัม เวียนนา เมลเบิร์น" -> "อัมสเตอร์ดัม เมลเบิร์น นิวยอร์ก เคียฟ เวียนนา" หรือ "ab ac bc" -> "ab bc ca" ปัญหาทำให้ฉันสนใจจากมุมมองของเชิงผสมและการค้นหาวิธีแก้ไข <h2>1. อัลกอริทึม</h2><h3>1.1. Brute-force</h3>อัลกอริธึมที่ง่ายที่สุดที่อยู่ในใจคือการค้นหาชุดค่าผสมที่เป็นไปได้ทั้งหมดจนกว่าจะพบชุดที่ต้องการ ข้อเสียเปรียบหลักคือจำนวนชุดค่าผสมที่เพิ่มขึ้นอย่างรวดเร็วและเร็วขึ้น - จำนวนชุดค่าผสมสำหรับ n คำจะเท่ากับแฟกทอเรียลและความซับซ้อนของอัลกอริทึมคือ O(n!) สำหรับ 3 คำ จะได้ชุดต่อไปนี้ - 6 ชุดค่าผสม: สำหรับ 4 คำ: Wikipediaแนะนำว่าสำหรับ 10 คำจะมีชุดค่าผสม 3.2 ล้านชุด และสำหรับ 100 คำ - ~10^158 ชุดค่าผสม การผ่านการผสมผสานหลายๆ อย่างดูค่อนข้าง... ยาก... <h3>1.2. การเพิ่มขึ้น</h3>ดังนั้น เราจำเป็นต้องมีอัลกอริธึมอื่น ไม่ใช่แค่การแจงนับ ตัวอย่างเช่น การรวมตามลำดับ: (1) รับคำแรก (2) นำคำถัดไปแล้วลองรวมเข้าด้วยกัน (ทางซ้ายหรือขวา) ) ไปที่อันแรก หากได้ผล ให้ทำซ้ำกับคำที่เหลือทั้งหมด (3) ถ้ารายการเริ่มต้นว่างเปล่า เราก็พบลำดับแล้ว ถ้าไม่ว่างเปล่า ล้มเหลว ให้ไปที่ (4) (4) เราถือว่าคำเริ่มต้นไม่ใช่คำแรก แต่เป็นคำที่สอง ฯลฯ ถ้าฉันจำไม่ผิด ความซับซ้อนของอัลกอริทึมนี้คือ O(n^2) ซึ่งน้อยกว่าอันแรกมาก ปัญหาคืออาจมีลำดับ (ค่อนข้างยาว) ซึ่งการขึ้นต้นด้วยอักขระใดๆ ไม่ได้นำไปสู่วิธีแก้ปัญหา - บรรทัดจะวนซ้ำและไม่สามารถต่อท้ายอักขระที่เหลือได้ โดยหลักการแล้ว มีตัวเลือกเพิ่มเติมที่เป็นไปได้ - หากไม่ได้ผล คุณสามารถไปในลำดับย้อนกลับ (กลับบรรทัดแล้วเริ่มใหม่) หรือสุ่มผสมคำ เป็นต้น สิ่งนี้คล้ายกับการเล่นปลอกนิ้ว - หากไม่ได้ผลเราจะพยายามผสมลูกบาศก์ในกล่องจนกว่าเราจะได้ลำดับที่ต้องการ จะต้องใช้เวลานานเท่าใดและจะทำงานได้หรือไม่ไม่มีความชัดเจน <h3>1.3. ลำดับแบบวน</h3>อัลกอริทึมนี้มีพื้นฐานอยู่บนแนวคิดง่ายๆ: หากเรามี 2 ลำดับที่ตรงตามเงื่อนไขของปัญหา ก็สามารถรวมกันเป็นลำดับเดียวได้หากมีอักขระที่ตัดกัน และอัลกอริธึมจะเป็นดังนี้: (1) แบ่งลำดับดั้งเดิมออกเป็น x ลำดับไซคลิกขั้นต่ำที่ตรงตามเงื่อนไขของปัญหา (2) รวมลำดับไซคลิกเป็นลำดับสุดท้ายเพียงลำดับเดียวที่ตรงตามเงื่อนไขของปัญหา เป็นที่น่าสังเกตว่าคำที่มีตัวอักษรตัวแรกและตัวสุดท้ายเหมือนกันในกรณีนี้ถือได้ว่าเป็นลำดับวงจรขั้นต่ำ และสามารถแนบกับคำอื่นในขั้นตอนที่ (1) หรือทิ้งไว้ในขั้นตอนที่ (2) ก็ได้ <h2>2. การใช้งาน</h2>โค้ดถูกโพสต์บนgithubนอกจากนี้ หากจำเป็น ฉันจะพูดถึง[ฟังก์ชั่น]ที่ใช้งานงานที่อธิบายไว้ <h3>2.1. ตัวต่อระดับประถมศึกษา</h3>ในระหว่างการนำไปใช้งาน คุณจะต้องอ้างอิงถึงตัวอักษรตัวแรกและตัวสุดท้ายของคำบ่อยมาก ดังนั้นคลาสที่นอกเหนือจากตัวคำนั้นเองยังใช้ตัวอักษรตัวแรกและตัวสุดท้ายของคำนั้นเป็นอิฐพื้นฐาน : :

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. การตรวจสอบลำดับดั้งเดิม</h3>ก่อนที่จะเริ่มอัลกอริธึมการค้นหาหลัก คุณควรตรวจสอบให้แน่ใจว่าตามหลักการแล้วปัญหาสามารถแก้ไขได้ ฉันใช้งานสิ่งนี้โดยใช้การตรวจสอบต่อไปนี้ (ต่อไปนี้ในย่อหน้านี้ S คือสตริงต้นทาง W คืออาร์เรย์ของ Word ที่สร้างขึ้นตามนั้น):

1. S ไม่เป็นโมฆะ ความยาว S > 0 (ก็ชัดเจน)
2. ใน W จำนวนและประเภทของอักขระตัวแรกและตัวสุดท้ายจะเหมือนกัน[ checkLetters()]
   ตัวอย่างเช่น สตริง "ab ba" สามารถแก้ไขได้และมี firstLetters = {a=1, b=1}, LastLetters = {a=1, b=1} และสตริง "ab ba bc" ไม่สามารถตัดสินใจได้และมี firstLetters = {a=
   1 , b=2 }, ตัวอักษรสุดท้าย = {a=1, b=1, c=1 }
   
3. ทุกคำ ในW เชื่อมต่อถึงกัน[checkConnectivity()] ตัวอย่างเช่น คำว่า "ab" ให้ความเชื่อมโยง [a,b] ในลำดับ "ab bc cd da" สัญลักษณ์ที่เชื่อมต่อกัน [a,b,c,d] ทั้งสองลำดับนี้สามารถตัดสินใจได้ แต่ลำดับ "ab bc ca fg gf" ไม่สามารถแก้ไขได้และมีบล็อกที่ตัดการเชื่อมต่อ 2 บล็อก: {[a,b,c] และ [f,g]} ฉันตรวจสอบการเชื่อมต่อโดยใช้ List<set<Character>> ดังนี้:
   • 3.1. เราใช้คำใดๆ ตรวจสอบว่าอักขระตัวแรก/ตัวสุดท้ายอยู่ใน Set<Character> ใดๆ หรือไม่
   • 3.2. หากไม่มี Set<Character> ใดที่มีตัวอักษรตัวแรกหรือตัวสุดท้าย ให้สร้าง Set<Character> ใหม่ด้วย
   • 3.3. หากเพียง 1 ชุด<ตัวละคร> มีตัวอักษรตัวแรก/ตัวสุดท้าย ให้เพิ่มตัวอักษรตัวอื่นในชุดนี้
   • 3.4. หาก 1 ชุดมีตัวอักษรตัวแรกและตัวที่สองอยู่ตัวสุดท้าย เราจะรวมชุดเหล่านี้เข้าด้วยกัน
   • 3.5. ทำซ้ำทุกคำ
   • 3.6. หากในรายการสุดท้าย<set<ตัวละคร>> มีเพียง 1 ชุด แสดงว่าลำดับมีการเชื่อมต่อหากมากกว่า 1 แสดงว่าไม่ได้เชื่อมต่อและไม่สามารถแก้ไขได้

<h3>2.3. ค้นหาลำดับสุดท้าย [generateResultLists()]</h3>ในการค้นหา เราต้องสร้างคลาส CycleList เพิ่มเติมซึ่งประกอบด้วย List<word> ที่ตรงตามเงื่อนไขของงาน เช่นเดียวกับ Set<Character> ซึ่งมีอักขระหลายตัวจากรายการ<words> "คุณลักษณะ" หลักของคลาสนี้คือความสามารถในการจัดเรียงใหม่เพื่อให้รายการเริ่มต้น (และสิ้นสุด) ด้วยตัวอักษรที่จำเป็นใด ๆ ที่รวมอยู่ในชุด <อักขระ> ตัวอย่างเช่น (จัดกลุ่มใหม่(b)) "ab bc ca" -> "bc ca ab" สิ่งนี้ช่วยให้คุณสามารถรวมแผ่นงาน 2 แผ่นที่มีจุดตัดของสัญลักษณ์ได้อย่างง่ายดาย - ก็เพียงพอแล้วที่จะจัดกลุ่มแผ่นงานทั้งสองใหม่ด้วยสัญลักษณ์ที่ตัดกันและคุณสามารถเพิ่มแผ่นงานหนึ่งไปยังอีกแผ่นงานได้ (อัลกอริทึมที่อธิบายไว้ข้างต้นนั้นใช้งานได้ค่อนข้างง่าย)

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. โดยสรุป</h2>ฉันชอบปัญหานี้มาก ฉันต้องใช้สมองจากมุมมองของอัลกอริทึม แต่ฉันไม่เสียใจเลย ในขณะที่รวมโค้ดผลลัพธ์ ฉันเริ่มเข้าใจการทำงานกับนิพจน์แลมบ์ดาและคอลเลกชันใน Java ดีขึ้น โค้ดที่อธิบายไว้ทำงานได้ค่อนข้างเร็ว บนพีซีที่ไม่ใช่เด็กอีกต่อไป อาร์เรย์ของคำแบบสุ่ม 30,000 คำจะถูกจัดเรียงในเวลาประมาณ 1 วินาที นอกเหนือจากโซลูชันที่อธิบายไว้แล้ว โค้ดบน Github ยังประกอบด้วย:

1. เครื่องกำเนิดลำดับแบบสุ่ม
2. คลาส SequenceAlgorithm ซึ่งใช้อัลกอริทึมจากส่วน (1.2)
3. ลำดับต่างๆ ที่ต้องทดสอบ เช่น การใช้ SequenceAlgorithm ของฉันไม่พบวิธีแก้ปัญหาสำหรับลำดับนี้ (ไม่ไปข้างหน้าหรือข้างหลัง): 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