詞鏈任務

在學習 Java.Multithreading 課程時，我對編寫單字鏈的任務非常感興趣： https: //javarush.com/tasks/com.javarush.task.task22.task2209。任務本身：給定一個單字鏈，必須以這樣的方式對它們進行排序：對於每對單詞，第一個單字的最後一個字母與下一個單字的第一個字母重合。當然，最終的鏈必須包含原始鏈的所有單字一次。例如，「基輔·紐約·阿姆斯特丹·維也納·墨爾本」->「阿姆斯特丹·墨爾本·紐約·基輔·維也納」或「ab ac bc」->「ab bc ca」。從組合學和尋找解決方案的角度來看，這個問題引起了我的興趣。 <h2>1。演算法</h2><h3>1.1。暴力破解</h3>我想到的最簡單的演算法是搜尋所有可能的組合，直到找到所需的組合。主要缺點是組合數量急劇增加 - n 個單字的組合數量將等於階乘，演算法的複雜度為 O(n!)。對於 3 個單詞，獲得以下集合 - 6 種組合： 對於 4 個單詞： 維基百科建議對於 10 個單詞，將有 320 萬個組合，對於 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 個 Set<character> 包含其第一個/最後一個字母 - 向該 Set 添加另一個字母
   • 3.4. 如果一組包含第一個字母，第二個字母包含最後一個字母，我們將這些組組合起來
   • 3.5. 對所有單字重複
   • 3.6. 如果最後List<set<character>>只包含1個集合，則序列是連通的，如果超過1個，則不連通，無法解析。

<h3>2.3。搜尋最終的序列[generateResultLists()]</h3>為了進行搜索，我們必須建立一個額外的類別CycleList，其中包含一個滿足任務條件的List<word>，以及一個Set<character>，其中包含List<words > 中的許多字元。該類別的主要「功能」是它能夠重新排列，以便清單以 Set<character> 中包含的任何必要字母開始（和結束）。例如，(regroup(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 中使用 lambda 表達式和集合。所描述的程式碼運行速度非常快；在我不再年輕的 PC 上，大約 1 秒內對 30,000 個隨機單字的陣列進行排序。 除了描述的解決方案之外，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