词链任务

在学习 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