Open UniqueAnagrams.java and implement the recursive method permutations that produces all the permutations of the characters in a string passed to the method as its argument. Take each character and follow it with all permutations of the remaining characters. For the character sequence abcd, begin with a and follow it with all permutations of the remaining characters, b, c, and d, to get: abcd, abdc, acbd, acdb, adbc, adcb. Then begin with the next character, b, in the original string and follow it with all permutations of the remaining characters, a, c, and d, to get: bacd, badc, bcad, bcda, bdac, and bdca. Continue in this fashion, by beginning with c and following it with all permutations of the remaining characters, a, b, and d, and finally by beginning with d and following it with all permutations of the remaining characters, a, b, and c.

To give more insight into the recursive solution, let's consider the step when we take b and follow it with all permutations of the remaining characters, a, c, and d. Let's represent this step as

b acd

A recursive call on acd would give us

ba cd

The recursive call on cd would result in

bac d

and the recursive call on d would be the base case and give us the permutation

bacd

Lets now consider the following two examples:

The character sequence abc has the following permutations: acb, bac, bca, cab, cba. In this example, all the characters are unique, so the permutations do not have duplicates.

However, the character sequence xbba has the following permutations: xbb, xbb, bxb, bbx, bxb, bbx. In this example, the recursive method produces all permutations, and when the characters repeat in the original sequence, there will be duplicates in the list of permutations.

Next implement sort method (and its helper methods getIndexOfSmallestAndRemoveDuplicates and swap) that should utilize the iterative selection sort algorithm to sort the permutations, and while sorting, remove duplicates. You need to call ArrayList methods like get and set to rearrange the elements in this.anagrams collection as appropriate.

public class UniqueAnagrams { private ArrayList anagrams; public UniqueAnagrams() { this.anagrams = new ArrayList<>(); } public void permutations(String word) { permutations("", word); System.out.println("Possible anagrams = " + this.anagrams); TreeSet toTest = new TreeSet(this.anagrams); System.out.println("Expected unique and sorted anagrams = " + toTest); System.out.println(); sort(); // duplicates will be removed during the sorting process } private void permutations(String prefix, String suffix) { int numOfChars = suffix.length(); if (numOfChars == 1) { //System.out.println(prefix + suffix); this.anagrams.add(prefix + suffix); } else { //TODO Project2  } } private void sort() { //TODO Project2   // calls getIndexOfSmallestAndRemoveDuplicates(index, this.anagrams.size()); // calls swap(index, indexOfNextSmallest); } private int getIndexOfSmallestAndRemoveDuplicates(int first, int last) { //TODO Project2   // as the smallest is being found removes duplicates return 0; // THIS IS A STUB } private void swap(int i, int j) { //TODO Project2  } private void display() { System.out.println("Computed unique and sorted anagrams = " + this.anagrams); } public static void main(String[] args) { UniqueAnagrams uniqueAnagrams = new UniqueAnagrams(); Scanner keyboard = new Scanner(System.in); System.out.println("Please enter a word"); String word = keyboard.next(); uniqueAnagrams.permutations(word); uniqueAnagrams.display(); } } 

Run #1:

Please enter a word

car

Generated anagrams = [car, cra, acr, arc, rca, rac]

Expected unique and sorted anagrams = [acr, arc, car, cra, rac, rca]

Computed unique and sorted anagrams = [acr, arc, car, cra, rac, rca]

Run #2:

Please enter a word

abc

Generated anagrams = [abc, acb, bac, bca, cab, cba]

Expected unique and sorted anagrams = [abc, acb, bac, bca, cab, cba]

Computed unique and sorted anagrams = [abc, acb, bac, bca, cab, cba]

Run #3:

Please enter a word

abba

Generated anagrams = [abba, abab, abba, abab, aabb, aabb, baba, baab, bbaa, bbaa, baab, baba, baba, baab, bbaa, bbaa, baab, baba, aabb, aabb, abab, abba, abab, abba]

Expected unique and sorted anagrams = [aabb, abab, abba, baab, baba, bbaa]

Computed unique and sorted anagrams = [aabb, abab, abba, baab, baba, bbaa]