Anagram algorithm returns duplicate values

Question

I am developing an algorithm for calculating anagrams for a given (set) of word (s). I just got it to work, with ONE incredibly frustrating exception (no pun intended, and the real exception was not ruled out). Despite my attempts to use efficient “clipping” to reduce the number of replicas, my algorithm adds a duplicate to the main list, in this case an object of the final static ArrayList (StringBuilder) () type. I can’t understand why this is happening. Below is my code; I decided to place the whole method for convenience.

This is a school assignment, so instead of the correct answer / solution, I am looking for recommendations / conceptual errors at my end.

EDIT: (code edited to avoid possible plagiarism before the appointment date.)

Here is an example:

**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 

Thanks for the help!:)

Answer 1

The obvious algorithm (just replacing letters) is a bit naive and does not consider the same letters as instances of the same letter. For example, if you have the word "eve", the two "e" are different from each other; if we single out the first E for illustration, you get combinations of " e ve" and "ev e " at different points in the process.

You need to somehow eliminate duplicates. The easiest way to do this is to assemble combos into a set of some types (for example, HashSet). It can contain only one element, so duplicates will be deleted.

Oh, and use String s, not StringBuilder s. I just noticed that you are doing this. StringBuilder does not override equals , so you are left with a version inherited from Object . Final result: for two StringBuilders a and b , a.equals(b) only if a == b .

Answer 2

One simple solution is to use Set to store your anagrams. This will take care of duplicate values.

I assume you are using a list, since your variable is called anagramList . You can find the JavaDoc for Set here: http://docs.oracle.com/javase/6/docs/api/java/util/Set.html

Answer 3

I would like to use Set to store anagrams, but use String, not StringBuilder, i.e.

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

The reason for not using StringBuilder is that hashCode does not change when it changes, as indicated in this example:

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

This will output the same hash code, which means that the StringBuilder hash code is not a reliable comparator for its contents.

Answer 4

This is a problem you encountered in your code. If there is a StringBuilder object for “squabble” in your list, the contains method returns false when you check whether your list contains another StringBuilder object for “squabble” after you create a “rattle” again (which happens because of the letter b occurs twice).

Checks if the object is in the list, and not if there is an object representing the same string.

Answer 5

You cannot use the contains () method to check if the contents of a string are there:

 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