単語の連鎖タスク

Java.Multithreading コースを受講している間、私は単語のチェーンを構成するタスク ( https://javarush.com/tasks/com.javarush.task.task22.task2209 ) に非常に興味を持ちました。タスク自体: 一連の単語が与えられた場合、各単語のペアについて、最初の単語の最後の文字が次の単語の最初の文字と一致するように並べる必要があります。当然のことながら、最後のチェーンには、元のチェーンのすべての単語が 1 回含まれている必要があります。たとえば、「キエフ ニューヨーク アムステルダム ウィーン メルボルン」 -> 「アムステルダム メルボルン ニューヨーク キエフ ウィーン」または「ab ac bc」 -> 「ab bc ca」です。この問題は、組み合わせ論と解決策の発見の観点から私にとって興味深いものでした。 <h2>1. アルゴリズム</h2><h3>1.1. ブルート フォース</h3>思い浮かぶ最も単純なアルゴリズムは、目的の組み合わせが見つかるまで、考えられるすべての組み合わせを検索することです。主な欠点は、組み合わせの数が急激に増加することです。n 個の単語の組み合わせの数は階乗に等しく、アルゴリズムの複雑さは O(n!) になります。3 つの単語の場合、次のセットが得られます - 6 つの組み合わせ: 4 つの単語の場合: Wikipedia では、10 単語の場合は 320 万の組み合わせがあり、100 単語の場合 - 〜 10^158 の組み合わせがあると示唆しています。これほど多くの組み合わせを検討するのは、少々... 難しそうに見えます... <h3>1.2. インクリメント</h3>したがって、列挙だけではなく、別のアルゴリズムが必要です。たとえば、順次結合です。(1) 最初の単語を取得し、(2) 次の単語を取得して、(左側または右側で) 結合しようとします。 ）最初に。うまくいったら、残りの単語すべてに対して繰り返します。(3) 最初のリストが空の場合、シーケンスが見つかった; 空でない場合は失敗、(4) に進む (4) 最初の単語ではなく 2 番目の単語を最初の単語として取得します。 私の記憶が間違っていなければ、このアルゴリズムの複雑さは O(n^2) で、最初のアルゴリズムよりもはるかに少ないです。問題は、どの文字で開始しても解決策が得られない (非常に長い) シーケンスが存在する可能性があることです。行がループになり、残りの文字を追加できなくなります。原理的には、さらに別のオプションも可能です。うまくいかない場合は、逆の順序 (行を逆にして最初からやり直す) を実行したり、単語をランダムに混ぜたりすることができます。これは指ぬき遊びに似ています。うまくいかない場合は、希望の順序が得られるまで箱の中でキューブを混ぜてみます。どのくらいの時間がかかるのか、うまくいくかどうかは不明です。<h3>1.3. 循環シーケンス</h3>このアルゴリズムは単純なアイデアに基づいています。つまり、問題の条件を満たす 2 つのシーケンスがあり、それらに交差する文字が含まれていれば、それらを 1 つに組み合わせることができます。 そして、アルゴリズムは次のようになります: (1) 元のシーケンスを問題の条件を満たす x 個の最小の巡回シーケンスに分割します。 (2) 巡回シーケンスを結合して、問題の条件を満たす 1 つの最終シーケンスを作成します。この場合、同じ最初と最後の文字を含む単語は最小限の循環シーケンスと見なすことができることに注意してください。そして、それらは段階 (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 は null ではなく、長さ 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 }、lastLetters = {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. 1 つのセットに最初の文字が含まれ、2 番目のセットに最後の文字が含まれている場合、これらのセットを結合します
   • 3.5. すべての単語に対して繰り返します
   • 3.6. 最終的に List<set<character>> に含まれるセットが 1 つだけの場合、シーケンスは接続されています。1 つ以上の場合、接続されておらず、解決できません。

<h3>2.3. 最終シーケンスを検索します [generateResultLists()]</h3>検索するには、タスクの条件を満たす List<word> と Set<character> を含む追加クラス CycleList を作成する必要がありました。 List<words> の多くの文字が含まれています。このクラスの主な「機能」は、Set<character> に含まれる必要な文字でリストが始まる (および終わる) ように再配置できる機能です。たとえば、(regroup(b)) "ab bc ca" -> "bc ca ab" となります。これにより、シンボルが交差する 2 つのシートを簡単にマージできます。交差するシンボルによって両方のシートを再グループ化するだけで十分で、1 つのシートをもう 1 つのシートに追加できます (上記のアルゴリズムは非常に簡単に実装されます)。

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 でのラムダ式とコレクションの操作についてよりよく理解できるようになりました。説明されているコードは非常に高速に動作し、私のもう若くない PC では、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