При проходженні курсу 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 слів: Вікіпедія підказує, що для 10 слів буде 3,2 млн. комбінацій, а для 100 слів - ~10^158 комбінацій. Перебрати таку кількість комбінацій виглядає дещо... скрутним... <h3>1.2. Отже, потрібен якийсь інший алгоритм, а не просто перебір, наприклад, послідовного приєднання: (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, створений на її основі):
- S не null, довжина S> 0 (ну, це очевидно)
- У 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 }. - Всі слова в 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 містить його першу/останню літеру - додаємо іншу літеру в цей Set
- 3.4. Якщо 1 сет містить першу літеру, а другу останню – об'єднуємо ці сети
- 3.5. Повторити всім слів
- 3.6. Якщо в результаті List містить тільки 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. Описаний код працює досить бадьоро, на моєму, вже не молодому ПК, масив із 30 000 випадкових слів упорядковується приблизно за 1 секунду. Код на гітхабі крім описаного рішення також містить:
- Генератор випадкових послідовностей
- Клас SequenceAlgorithm, який реалізує алгоритм із розділу (1.2)
- Декілька послідовностей для тестування, наприклад, моя реалізація SequenceAlgorithm не знаходить рішення для такої послідовності (ні в прямому, ні в зворотному напрямку): LK Ud aa LL WY OK lQ cK 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
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ