Nhiệm vụ chuỗi từ

Khi tham gia khóa học Java.Multithreading, tôi rất hứng thú với nhiệm vụ soạn một chuỗi từ: https://javarush.com/tasks/com.javarush.task.task22.task2209 . Bản thân nhiệm vụ: cho một chuỗi từ, cần phải sắp xếp chúng sao cho đối với mỗi cặp từ, chữ cái cuối cùng của từ đầu tiên trùng với chữ cái đầu tiên của từ tiếp theo. Đương nhiên, chuỗi cuối cùng phải bao gồm tất cả các từ của chuỗi ban đầu một lần. Ví dụ: "Kiev New York Amsterdam Vienna Melbourne" -> "Amsterdam Melbourne New York Kiev Vienna" hoặc "ab ac bc" -> "ab bc ca". Vấn đề khiến tôi quan tâm từ quan điểm của tổ hợp và tìm ra giải pháp. <h2>1. Thuật toán</h2><h3>1.1. Brute-force</h3>Thuật toán đơn giản nhất mà tôi nghĩ đến là tìm kiếm qua tất cả các kết hợp có thể có cho đến khi tìm thấy kết hợp mong muốn. Nhược điểm chính là số lượng kết hợp tăng mạnh và nhanh chóng - số lượng kết hợp cho n từ sẽ bằng giai thừa và độ phức tạp của thuật toán là O(n!). Đối với 3 từ, thu được bộ sau - 6 kết hợp: Đối với 4 từ: Wikipedia gợi ý rằng đối với 10 từ sẽ có 3,2 triệu kết hợp và đối với 100 từ - ~10^158 kết hợp. Trải qua nhiều cách kết hợp như vậy có vẻ hơi... khó khăn... <h3>1.2. Tăng</h3>Vì vậy, chúng ta cần một số thuật toán khác chứ không chỉ liệt kê, ví dụ: nối tuần tự: (1) Lấy từ đầu tiên, (2) Lấy từ tiếp theo và cố gắng nối nó (ở bên trái hoặc bên phải ) đến số đầu tiên. Nếu nó hoạt động, lặp lại cho tất cả các từ còn lại. (3) Nếu danh sách ban đầu trống, chúng ta đã tìm thấy dãy; nếu nó không trống, thất bại, hãy chuyển đến (4) (4) Chúng ta lấy từ đầu tiên không phải là từ đầu tiên mà là từ thứ hai, v.v. Nếu tôi không nhầm thì độ phức tạp của thuật toán này là O(n^2), nhỏ hơn nhiều so với thuật toán đầu tiên. Vấn đề là có thể có các chuỗi (khá dài) mà việc bắt đầu bằng bất kỳ ký tự nào không dẫn đến giải pháp - dòng sẽ bị lặp và các ký tự còn lại không thể được nối thêm. Về nguyên tắc, có thể có các tùy chọn khác - nếu nó không hoạt động, bạn có thể thực hiện theo thứ tự ngược lại (đảo ngược dòng và bắt đầu lại) hoặc trộn ngẫu nhiên các từ, v.v. Điều này tương tự như chơi thimbles - nếu không thành công, chúng ta sẽ cố gắng trộn các khối trong hộp cho đến khi đạt được trình tự mong muốn. Sẽ mất bao lâu và liệu nó có hiệu quả hay không vẫn chưa rõ ràng. <h3>1.3. Chuỗi tuần hoàn</h3>Thuật toán này dựa trên một ý tưởng đơn giản: nếu chúng ta có 2 chuỗi thỏa mãn điều kiện của bài toán thì chúng có thể được kết hợp thành một nếu chúng chứa các ký tự giao nhau. Và thuật toán sẽ như sau: (1) Chia dãy ban đầu thành x dãy tuần hoàn tối thiểu thỏa mãn điều kiện của bài toán (2) Kết hợp các dãy tuần hoàn thành một dãy cuối cùng thỏa mãn điều kiện của bài toán. Điều đáng chú ý là các từ chứa cùng chữ cái đầu và chữ cái cuối trong trường hợp này có thể được coi là chuỗi tuần hoàn tối thiểu. Và chúng có thể được gắn với các từ khác ở giai đoạn (1) hoặc để lại ở giai đoạn (2). <h2>2. Triển khai</h2>Mã được đăng trên github , hơn nữa, nếu cần, tôi sẽ đề cập đến [các chức năng] thực hiện nhiệm vụ được mô tả. <h3>2.1. Gạch cơ bản</h3>Trong quá trình triển khai, bạn sẽ phải thường xuyên tham khảo các chữ cái đầu tiên và cuối cùng của một từ, do đó, một lớp chứa, ngoài chính từ đó, còn có các chữ cái đầu tiên và cuối cùng của nó được sử dụng làm gạch cơ bản :

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. Kiểm tra trình tự ban đầu</h3>Trước khi bắt đầu thuật toán tìm kiếm chính, bạn nên đảm bảo rằng về nguyên tắc, vấn đề có thể giải được. Tôi đã triển khai điều này bằng cách sử dụng các bước kiểm tra sau (sau đây trong đoạn này, S là chuỗi nguồn, W là mảng Word được tạo dựa trên nó):

1. S không rỗng, độ dài S > 0 (điều đó là hiển nhiên)
2. Trong W, số lượng và kiểu ký tự đầu tiên và cuối cùng giống nhau [checkLetters()] .
   Ví dụ: chuỗi "ab ba" có thể giải được và chứa firstLetters = {a=1, b=1}, LastLetters = {a=1, b=1}, Và chuỗi "ab ba bc" là không thể giải quyết được và chứa firstLetters = {a=
   1 , b=2 }, LastLetters = {a=1, b=1, c=1 }.
   
3. Tất cả các từ trong W đều được kết nối với nhau [checkConnectivity()] . Ví dụ: từ "ab" cung cấp tính kết nối [a,b], trong chuỗi "ab bc cd da" các ký hiệu được kết nối [a,b,c,d], cả hai chuỗi này đều có thể quyết định được. Nhưng dãy "ab bc ca fg gf" không thể giải được và chứa 2 khối bị ngắt kết nối: {[a,b,c] và [f,g]}. Tôi đã kiểm tra kết nối bằng List<set<character>> như sau:
   • 3.1. Chúng tôi lấy bất kỳ từ nào, kiểm tra xem ký tự đầu tiên/cuối cùng của nó có được chứa trong bất kỳ Set<character> nào không
   • 3.2. Nếu không có Set<character> nào chứa chữ cái đầu tiên hoặc cuối cùng của nó - hãy tạo một Set<character> mới với chúng
   • 3.3. Nếu chỉ có 1 Bộ<ký tự> chứa chữ cái đầu/cuối của nó - hãy thêm một chữ cái khác vào Bộ này
   • 3.4. Nếu 1 bộ chứa chữ cái đầu tiên và bộ thứ hai chứa chữ cái cuối cùng thì chúng ta kết hợp các bộ này
   • 3.5. Lặp lại cho tất cả các từ
   • 3.6. Nếu cuối cùng List<set<character>> chỉ chứa 1 bộ thì chuỗi được kết nối , nếu nhiều hơn 1 thì chuỗi đó không được kết nối và không thể giải quyết được.

<h3>2.3. Tìm kiếm chuỗi cuối cùng [generateResultLists()]</h3>Để tìm kiếm, chúng tôi phải tạo một lớp CycleList bổ sung, chứa Danh sách<word> thỏa mãn các điều kiện của nhiệm vụ, cũng như Tập hợp<ký tự>, chứa nhiều ký tự trong Danh sách<words>. "Tính năng" chính của lớp này là khả năng sắp xếp lại sao cho Danh sách bắt đầu (và kết thúc) bằng bất kỳ chữ cái cần thiết nào có trong Tập hợp<ký tự>. Ví dụ: (regroup(b)) "ab bc ca" -> "bc ca ab". Điều này cho phép bạn dễ dàng hợp nhất 2 trang tính có giao điểm của các ký hiệu - chỉ cần nhóm lại cả hai trang bằng ký hiệu giao nhau là đủ và bạn có thể thêm trang này vào trang kia (thuật toán mô tả ở trên được thực hiện khá dễ dàng).

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. Tóm lại</h2>Tôi thực sự thích vấn đề này, tôi đã phải vắt óc từ góc nhìn của thuật toán, nhưng tôi không hối hận chút nào. Trong khi kết hợp mã kết quả, tôi bắt đầu hiểu rõ hơn cách làm việc với các biểu thức và bộ sưu tập lambda trong Java. Mã được mô tả hoạt động khá nhanh; trên chiếc PC không còn non trẻ của tôi, một mảng gồm 30.000 từ ngẫu nhiên được sắp xếp trong khoảng 1 giây. Ngoài giải pháp được mô tả, mã trên Github còn chứa:

1. Trình tạo chuỗi ngẫu nhiên
2. Lớp SequenceAlgorithm, triển khai thuật toán từ phần (1.2)
3. Một số trình tự cần kiểm tra, ví dụ: việc triển khai Thuật toán trình tự của tôi không tìm thấy giải pháp cho trình tự này (không tiến cũng không lùi): 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