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

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; 
     } 
    } 
} 

Любая помощь будет много appriciated !!

Answer 1

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

• Рефлексивность: х ≤ х всегда верно.
• Антисимметрия: Если х ≤ у и х ≠ у, то у ≤ х никогда не верно.
• транзитивность: Если х ≤ у и у ≤ г, то х ≤ г
• Целостность: Для любого х и у, имеют по крайней мере один из й ≤ у и у ≤ х.

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

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

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

Answer 2

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

Answer 3

Подход 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 

Answer 4

Это эквивалентно к этой проблеме: Detecting when matrix multiplication is possible

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