Lab 10 Exam Anagrams
An anagram is a permutation of characters in a string to produce an English
word. Many word games, like Scrable, depend on your ability to find
anagrams. In this lab you will write a program that will produce all the
anagrams from a given string. To do this your program will need to have
access to a list of English words. There is such a file in /usr/share/dict/words.
This is a text file with one word per line in alphabetical order.
What your program will do
Open the file /usr/share/dict/words. Read in each line
of the file and add to a SortedArrayList object called wordList. Prompt
the user to enter any string of characters. Compute all the permutations
of this string, checking each against wordList. Each permutation that is
in wordList is printed. The program continues to prompt the user for the
next string of characters until the user enters ctrl-d. A working version
of this program is in /home/teterwa/csc223/lab10 called Anagram.
Program design
Your program will have three classes: SortedArrayList,
Permutations, and Anagram. Place your code in a directory called
lab10. Please do not include the dictionary in the directory.
Anagram
This class will contain the main method. This method
will need to open a text file, read in each line and place each line into a
SortedArrayList and then process user queries which will come from System.in.
You will find the sample code on page 56 and page 54 extremely useful. The
text file that contains the English words is already sorted. So while you
could use the add() method you wrote for SortedArrayList it would be far more
efficient to create a new add method, called addAtEnd(AT ob) which adds ob to
the end of the SortedArrayList. This speeds up the complexity of adding
one word to the SortedArrayList from order n to constant order. You
can make your program even more efficient if you avoid having to
"resize" the array. You can find out how many words are in the
dictionary file by using the linux utility wc (which stands for word
count). It counts the number of lines, words and characters in a text
file. You should write an alternate constructor for the SortedArrayList
file that has an int parameter and uses this int to set the initial size of the
array. Thus, you will avoid the need to resize. I suggest you add
another method called isSorted() to your SortedArrayList class and use it after
the wordList is built to be
sure that the words your program read in from the dictionary file really were in
sorted order.
Permuations
This class has a constructor that creates a (private)
arrayList of all the permuations of any String that is passed as a parameter to
the constructor. There is an accessor method to this arrayList called
getPerms() that returns an ArrayList<String> of all the
permutations. You can use my Permutations class by copying the file Permuations.class
to your directory. For extra credit write your own Permutations.java
class.
SortedArrayList
You can use the SortedArrayList class you developed last week
or mine which is available in /home/teterwa/public/csc223/lab9. Add to
this class a method addAtEnd(AT ob) which adds the object ob to the end of the
array and has the precondition that ob is greater than any object already in the
array. Write a method call isSorted() which returns a boolean reflecting
whether or not the array is sorted. Add a Constructor with an int
parameter which is used to set the initial size of the array
field.