단어 연결 작업

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개 단어의 경우: Wikipedia에서는 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는 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<문자> 중 첫 번째 또는 마지막 문자가 포함되어 있지 않으면 해당 문자로 새 Set<문자>를 만듭니다.
   • 3.3. 1개의 Set<문자>에만 첫 번째/마지막 문자가 포함되어 있는 경우 - 이 세트에 다른 문자를 추가하세요.
   • 3.4. 1 세트에 첫 번째 문자가 포함되고 두 번째 문자가 마지막 문자가 포함된 경우 이 세트를 결합합니다.
   • 3.5. 모든 단어에 대해 반복
   • 3.6. 결국 List<set<character>>에 1개의 세트만 포함되어 있으면 시퀀스가 ​​연결되고 , 1보다 많으면 연결되지 않고 확인할 수 없습니다.

<h3>2.3. 최종 시퀀스 검색 [generateResultLists()]</h3> 검색을 위해 작업 조건을 만족하는 List<word>와 Set<character>를 포함하는 CycleList 클래스를 추가로 만들어야 했습니다. List<words>의 많은 문자가 포함되어 있습니다. 이 클래스의 주요 "특징"은 목록이 Set<character>에 포함된 필수 문자로 시작하고 끝나도록 재배열하는 기능입니다. 예를 들어 (재그룹화(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에서 람다 식 및 컬렉션 작업을 더 잘 이해하기 시작했습니다. 설명된 코드는 매우 빠르게 작동합니다. 더 이상 젊지 않은 PC에서는 30,000개의 임의 단어 배열이 약 1초 만에 정렬됩니다. 설명된 솔루션 외에도 Github의 코드에는 다음이 포함되어 있습니다.

1. 무작위 시퀀스 생성기
2. 섹션 (1.2)의 알고리즘을 구현하는 SequenceAlgorithm 클래스
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