Must be done using Stacks and Queues

In this lab assignment, you will create a Java application that uses a stack to return a list containing all permutations of a given string, and then checks to see which ones are English words. You will read words from a file and create and check the permutations for each word. For example, there are six permutations of the letters in the string tra:

 tra, rta, rat, tar, atr, art 

Generating Permutations

In general, a string with n distinct letters has n! ("n factorial") permutations. For instance, a 4-letter string has 4! = 24 permutations, a 5-letter string has 5! = 120 permutations, a 6-letter string has 6! = 720 permutations, and so on. To help you get started, here is some pseudocode. Suppose you want to find all permutations of the string tra:

 Push the string +tra onto a stack While the stack is not empty Pop off the top of the stack. if that string ends in a + (such as tra+) Remove the + and add the string to the list of permutations else for each letter to the right of the + Remove the letter from the right of the + Insert it just before the + Push the resulting string onto the stack. 

For example, if you pop a+cre, then you will push ac+re, ar+ce, ae+cr.

When the string you are using contains duplicate letters, a simple permutations generator will yield some duplicate permutations. For instance, the permutations of "dda" will generate the 3! = 6 permutations

 dda, dda, dad, dad, add, add 

Checking for English Words

Next, your program will determine which of the permutations is an English word by looking them up in a dictionary. Filtering out the English words yields: dad, dad, add, add In such cases, your program should also filter out duplicates to yield the final list: dad, add.

Requirements

Your implementation should include a PermutationsConsole class (this is the client class, driver class, or console class) and a PermutationsCalculator. You will use the Dictionary class from lab 1.

PermutationsCalculator class:

Fields:

• a stack for calculating the permutations; you can find the stack implementation in Canvas under Files.
• an ArrayList to hold all permutations
• an ArrayList to hold unique permutations.
• an ArrayList to hold the unique English words from the permuatations

Methods:

• ArrayList allPermutations(String word) will find all the permutations of the parm, store them in the all permutations ArrayList and return that ArrayList.
• ArrayList uniquePermutations(String word) will find all the unique permutations, store them in the unique permutations ArrayList and return that ArrayList.
• ArrayList uniqueWords(String word) will find the unique English words in the all permutations ArrayList, store them in the unique words ArrayList, and return that ArrayList.
• int numDuplicates() will return the number of duplicate permutations found.

PermutationsConsole class:

1. Create an output file named "perms.txt".
2. Create an output file named "analytics.txt".
3. Prompt for the name of the dictionary file, then call the Dictionary constructor to read the words and create the dictionary.
4. Create an unbounded queue to store words; you can find the queue implementation in Canvas under Files.
5. Use a loop to read words from the keyboard until the user wants to stop; store each word in the queue.
6. For each word in the queue:
   1. Dequeue the word, create a PermutationsCalculator and find all permutations, the unique permutations, and the unique English words.
   2. Print the original word, all permutations of the word, all unique permutations of the word and all the unique English words to the output file.
   3. Calculate and print to the analytics file the following for each word: the word itself, the total number of permutations, the number of duplicate permutations, the percentage of permutations which were duplicates, the number of English words and the percentage of permutations which were English words.
7. Calculate the following overall analytics and print them to the analytics file: the total number of words input by the user, the average length of the words input by the user, the total number of permutations generated, the total number of English words found, and the percentage of permutations which were English words.

Do not put all the code in the main method. Use other methods to do some of the work. Clearly label all the output written to the output files. Make sure the output files are nicely formatted.