Создание компаратора для упорядочения слов так, чтобы последняя буква каждого слова была первой буквой следующего слова?

Question

Хорошо, у меня есть программа с частью, которая мне нужна: "Упорядочить слова так, чтобы последняя буква каждого элемента в списке была первой буквой следующего элемента, своего рода цепочка слов, связанных друг с другом последние и первые буквы. "

Пример ввода: собака, слон, жираф, носорог, тигр и правильный вывод - собака, жираф, слон, тигр, носорог в то время как мой вывод - тигр, носорог, собака, жираф, слон.

Компаратор такой:

class linkedSort implements Comparator {
    //will return 1 for a match
    //returns 0 if no match

    public int compare(Object t, Object t1) {
        char[] charArr1 = t.toString().toCharArray();
        char[] charArr2 = t1.toString().toCharArray();

        if (charArr1[charArr1.length - 1] == charArr2[0]) {
            return -1;
        } else {
            return 1;
        }
    }
}

Любая помощь будет очень ценной !!

Answer 1

Вы не можете решить это с помощью простого компаратора и сортировки, потому что сравнение не определяет итоговый заказ .Общий порядок - это тот, в котором выполняются следующие четыре свойства:

• Отражательная способность : x ≤ x всегда истинно.
• Антисимметрия : Если x ≤ y и x ≠ y, то y ≤ x никогда не верна.
• Транзитивность : Если x ≤ y и y ≤ z, то x ≤ z
• Совокупность : Для любых x и y выполняется хотя бы один из x ≤ y и y ≤ x.

Ваш заказ не является итоговым.Во-первых, это нарушает рефлексивность: например, «a» ≤ «a».Во-вторых, он нарушает антисимметрию: «легкость» ≤ «ева» и «ева» ≤ «легкость».В-третьих, он нарушает транзитивность: «восток» ≤ «чай» и «чай» ≤ «авер», но «восток» ≤ «авер» ложен.Наконец, оно не является полным: «восток» не меньше, чем «запад», а «запад» не меньше, чем «восток».

Чтобы решить эту проблему, вам нужно подойти к ней по-другому.В качестве подсказки вы можете подумать о проблеме как о графике, где буквы - это узлы, а слова - ребра, соединяющие начальную и конечную буквы.Можете ли вы найти на этом графике путь, который посещает каждое ребро ровно один раз?

Надеюсь, это поможет!

Answer 2

Если вы надеетесь сделать это с sort, то это не сработает.Компаратор должен наложить на коллекцию общее количество , но ваши требования не такие.

Answer 3

Это эквивалентно этой проблеме: Определение возможности умножения матриц

1. Создать узел для каждой буквы
2. Соединить две буквы с направленным ребром для соответствующего животного (разрешить несколько ребер между одной парой вершин)
3. Найдите эулярийскую тропу

Answer 4

Подход Comparator не сработает. Сортировка использует только локальные сравнения, но ваша проблема - глобальная оптимизация.

Для иллюстрации приведу фактические сравнения с Arrays.sort(array, comparator). Обратите внимание, что некоторые из свопов нарушают правильный выбор, сделанный ранее, потому что они имеют только локальные знания.

start: dog,elephant,giraffe,rhinoceros,tiger

dog, elephant (swap)

-> elephant,dog,giraffe,rhinoceros,tiger

dog, giraffe (OK)

-> elephant,dog,giraffe,rhinoceros,tiger

giraffe, rhinoceros (swap)

-> elephant,dog,rhinoceros,giraffe,tiger

dog, rhinoceros (swap)

-> elephant,rhinoceros,dog,giraffe,tiger

elephant, rhinoceros (swap)

-> rhinoceros,elephant,dog,giraffe,tiger

giraffe, tiger (swap)

-> rhinoceros,elephant,dog,tiger,giraffe

dog, tiger (swap)

-> rhinoceros,elephant,tiger,dog,giraffe

elephant, tiger (OK)

-> rhinoceros, elephant, tiger, dog, giraffe