Алгоритм анаграммы возвращает повторяющиеся значения

Question

Я разрабатываю алгоритм для вычисления анаграмм для заданного (набора) слов (ов). Я просто получил его на работу, с ОДНОМ невероятно расстраивающим исключением (ни каламбур не предназначался, и не было исключено настоящее исключение). Несмотря на мои попытки использовать эффективную «обрезку» для уменьшения количества реплик, мой алгоритм добавляет дубликат в главный список, в этом случае объект типа final static ArrayList (StringBuilder)(). Я не могу понять, почему это происходит. Ниже мой код; я решил опубликовать весь метод для удобства.

Это задание для школы, поэтому вместо правильного ответа/решения я ищу руководство/концептуальные ошибки на моем конце.

EDIT: (код вырезаны, чтобы избежать возможного плагиата до начала срока выполнения задания в.)

Вот пример:

**input:** 
pnxish 
bauelqbs 
coxiuqit 
elbarcbs 
ptos 

**output:** 
Now printing anagrams: 
Anagram #0: sphinx 
Anagram #1: squabble 
Anagram #2: squabble 
Anagram #3: quixotic 
Anagram #4: quixotic 
Anagram #5: scrabble 
Anagram #6: scrabble 
Anagram #7: pots 
Anagram #8: post 
Anagram #9: tops 
Anagram #10: opts 
Anagram #11: spot 
Anagram #12: stop 

Спасибо за помощь! :)

Answer 1

Очевидный алгоритм (просто замена букв) немного наивна и не рассматривает одинаковые буквы как экземпляры одной и той же буквы. Например, если у вас есть слово «eve», два «e» отличаются друг от друга; если мы выделяем первый E для иллюстрации, вы получаете комбинации типа «e v e» и «e v e» в разных точках процесса.

Вам необходимо как-то устранить дубликаты. Самый простой способ сделать это - собрать комбо в набор некоторых типов (например, HashSet). Он может содержать только один элемент, поэтому дубликаты будут эффективно удалены.

О, и использовать String s, а не StringBuilder s. Я просто заметил, что вы это делаете. StringBuilder не переопределяет equals, поэтому вы остаетесь с версией, унаследованной от Object. Конечный результат: для двух StringBuilders a и b, a.equals(b) только если a == b.

Answer 2

Одним из простых решений является использование Set для хранения ваших анаграмм. Это обеспечит дублирование значений.

Я предполагаю, что вы используете список, так как ваша переменная имеет имя anagramList. Вы можете найти JavaDoc для Set здесь: http://docs.oracle.com/javase/6/docs/api/java/util/Set.html

Answer 3

Я хотел бы посмотреть, чтобы использовать набор для хранения анаграммы, но использовать строку, а не StringBuilder, т.е.

Set<String> anagrams = new HashSet<String>(); 

Причина не использовать StringBuilder, что хэш-код не меняется при изменении его, как указано в этом примере:

StringBuilder sb = new StringBuilder(); 
System.out.println(sb.hashCode()); 
sb.append('c'); 
System.out.println(sb.hashCode()); 

Это будет выводить тот же хэш-код, это означает, что хэш-код из StringBuilder не является надежным компаратором для его содержания.

Answer 4

Это проблема, с которой вы столкнулись в своем коде.Если в вашем списке есть объект StringBuilder для «squabble», метод contains возвращает false, когда вы проверяете, содержит ли ваш список другой объект StringBuilder для «ссориться» после того, как вы снова создадите «скрежет» (что происходит из-за буквы b происходит дважды).

Содержимое содержит проверку того, находится ли объект в списке, а не если объект представляет одну и ту же строку.

Answer 5

Вы не можете использовать содержит метод(), чтобы проверить, является ли содержание строки сама там:

List<StringBuilder> list = new ArrayList<StringBuilder>();  
StringBuilder sb = new StringBuilder("hello"); 
list.add(sb); 
StringBuilder sb2 = new StringBuilder("hello"); 
System.out.println(list.contains(sb2)); 
//echos false