Generating anagrams with recursive backtracking.
An anagram is a word or phrase made by rearranging the letters of another word or phrase. For example, the words “midterm” and “trimmed” are anagrams. If you ignore spaces and capitalization and allow multiple words, a multi-word phrase can be an anagram of some other word or phrase. For example, the phrases “Clint Eastwood” and “old west action” are anagrams.
AnagramSolver class that uses recursive backtracking to print all anagram phrases of a given word or phrase.
public AnagramSolver(List<String> dictionary)
- Initializes a new
AnagramSolverobject using the given
dictionary, precomputing all of the letter inventories in advance and storing them in a
HashMap(Note that we should be using a
HashMapand not a
LinkedHashMap). This method should not change the list in any way. Assume that the
dictionaryis a non-empty collection of non-empty sequences of letters, and that it contains no duplicates.
public void print(String text, int max)
- Prints all anagrams of
textthat include at most
maxwords (or an unlimited number of words if
maxis 0) to
System.outusing an optimized recursive backtracking algorithm. Do not make any assumptions about the length of the input or output if
maxis 0. Throw an
maxis less than 0.
Represent text using
LetterInventory objects to keep track of counts of each letter in the text. By choosing this abstraction, we can now rely on the
subtract method to figure out when one group of letters can be formed from another group of letters.
LetterInventory letters = new LetterInventory("midterm"); LetterInventory candidate = new LetterInventory("term"); letters.subtract(candidate); // [dim]
Since the result of
letters.subtract(candidate) is not
candidate could be one of the words in an anagram phrase for
Stack and then print the resulting data structure. On each recursive call, search the
dictionary from beginning to end and to explore each word that is a match for the current set of letters. The possible solutions should be explored in the same order as they appear in the given
dictionary file. Note that if you are removing from your
List, there are two versions of the
remove method. One that removes an element at an index and one that removes the first occurence of an element in your
List; it is up to you to decide which one is best suited for this program. You should start by implementing this method without considering
max, and then add logic for
Once you have a working
To test the pruning optimization, print the size of the original dictionary and the pruned dictionary and manually check that the output matches what you would expect for the
eleven.txt dictionary. As another example, when processing “george bush” on
dict1.txt, the original dictionary of size 56 is pruned to a new dictionary of size 31.
Suppose we want to print all anagrams of “eleven plus two” given the dictionary file
The letters in “eleven plus two” do not support all the words in the dictionary. In particular, “potato” and “zebra” contain letters (“a” and “z”, respectively) that are not in
elevenplustwo. So, we prune the dictionary to the following:
Using the pruned dictionary, we explore the possible anagram words with recursive backtracking, keeping track of the remaining letters at each recursive call.
Welcome to the cse143 anagram solver. What is the name of the dictionary file? eleven.txt phrase to scramble (return to quit)? eleven plus two Max words to include (0 for no max)? 0 [one, plus, twelve] [one, twelve, plus] [plus, one, twelve] [plus, twelve, one] [twelve, one, plus] [twelve, plus, one] phrase to scramble (return to quit)?
"george bush" example with dict0.txt
explore [beegghorsu] bee choose bee explore [gghorsu] bee go choose go explore [ghrsu] bee go gush choose gush explore [r] bee go gush shrug unchoose shrug choose shrug explore  print [bee, go, shrug] unchoose unchoose gush choose gush explore [gor] bee go choose go explore [r] bee go gush shrug unchoose gush shrug unchoose shrug choose shrug explore [go] bee go choose go explore  print [bee, shrug, go] unchoose gush shrug unchoose unchoose go choose go explore [beeghrsu] bee choose bee explore [ghrsu] bee go gush choose gush explore [r] bee go gush shrug unchoose shrug choose shrug explore  print [go, bee, shrug] unchoose unchoose go gush choose gush explore [beer] bee choose bee explore [r] bee go gush shrug unchoose go gush shrug unchoose shrug choose shrug explore [bee] bee choose bee explore  print [go, shrug, bee] unchoose go gush shrug unchoose unchoose gush choose gush explore [beegor] bee choose bee explore [gor] bee go choose go explore [r] bee go gush shrug unchoose gush shrug unchoose go choose go explore [beer] bee choose bee explore [r] bee go gush shrug unchoose go gush shrug unchoose gush shrug unchoose shrug choose shrug explore [beego] bee choose bee explore [go] bee go choose go explore  print [shrug, bee, go] unchoose gush shrug unchoose go choose go explore [bee] bee choose bee explore  print [shrug, go, bee] unchoose go gush shrug unchoose gush shrug unchoose
In terms of external correctness, your class must provide all of the functionality described above. In terms of style, we will be grading on your use of comments, good variable names, consistent indentation and good coding style to implement these operations.
There are several places where unnecessary or repeated logic is typically introduced.
- Don’t compute a value more than once if it doesn’t need to be recomputed.
- Don’t continue to explore recursive branches that will never be printed.
- Don’t introduce unnecessary base cases or recursive cases.
Your class may have other methods besides those specified, but any other methods you add should be
Create a new file
reflection.txt and write a paragraph-long reflection answering the following questions (along with anything else you find appropriate):
- What did you learn this week?
- What did you enjoy in the course this week?
- What did you find challenging or frustrating this week?
- What did you find particularly helpful for your learning this week?
reflection.txt to Grade-It!