An anagram is formed by rearranging the letters of a word. Anagrams are often us

Question

An anagram is formed by rearranging the letters of a word. Anagrams are often used in word games, and forming anagrams is a special case of generating the possible permutations (rearrangements) of a sequence, a problem that pops up frequently in many areas of computing and mathematics. For example, the possible anagrams of the word "you" is the list ["you", "yuo", "uyo", "uoy", "oyu", "ouy"]. 1. Write a program named Anagrams that takes a single word of any length (string). String can be entered run-time via keyboard or as an input parameter as well. 2. The program should find and output all possible anagrams of the string first using an iterative algorithm IterativeAnagram (). 3. Write a second function named RecursiveAnagram () that process the same word and output the all possible anagrams of the string using a recursive approach. 4 By calculating the time (you may find the java.time class helpful) it takes to run each program for various sizes of inputs, determine the order of each algorithm.

Explanation / Answer

import java.util.ArrayList;

public class Anagram {

   /**
   * List permutation of a string
   *
   * @param s the input string
   * @return the list of permutation
   */
   public static ArrayList<String> recursiveAnagaram(String s) {
   // The result
   ArrayList<String> res = new ArrayList<String>();
   // If input string's length is 1, return {s}
   if (s.length() == 1) {
   res.add(s);
   } else if (s.length() > 1) {
   int lastIndex = s.length() - 1;
   // Find out the last character
   String last = s.substring(lastIndex);
   // Rest of the string
   String rest = s.substring(0, lastIndex);
   // Perform permutation on the rest string and
   // merge with the last character
   res = merge(recursiveAnagaram(rest), last);
   }
   return res;
   }

   /**
   * @param list a result of permutation, e.g. {"ab", "ba"}
   * @param c the last character
   * @return a merged new list, e.g. {"cab", "acb" ... }
   */
   public static ArrayList<String> merge(ArrayList<String> list, String c) {
   ArrayList<String> res = new ArrayList<String>();
   // Loop through all the string in the list
   for (String s : list) {
   // For each string, insert the last character to all possible postions
   // and add them to the new list
   for (int i = 0; i <= s.length(); ++i) {
   String ps = new StringBuffer(s).insert(i, c).toString();
   res.add(ps);
   }
   }
   return res;
   }

public static void iterativeAnagram(String s) {
// Print initial string, as only the alterations will be printed later
System.out.println(s);   
char[] a = s.toCharArray();
int n = a.length;
int[] p = new int[n]; // Weight index control array initially all zeros. Of course, same size of the char array.
int i = 1; //Upper bound index. i.e: if string is "abc" then index i could be at "c"
while (i < n) {
if (p[i] < i) { //if the weight index is bigger or the same it means that we have already switched between these i,j (one iteration before).
int j = ((i % 2) == 0) ? 0 : p[i];//Lower bound index. i.e: if string is "abc" then j index will always be 0.
swap(a, i, j);
// Print current
System.out.println(join(a));
p[i]++; //Adding 1 to the specific weight that relates to the char array.
i = 1; //if i was 2 (for example), after the swap we now need to swap for i=1
}
else {
p[i] = 0;//Weight index will be zero because one iteration before, it was 1 (for example) to indicate that char array a[i] swapped.
i++;//i index will have the option to go forward in the char array for "longer swaps"
}
}
}
private static String join(char[] a) {
StringBuilder builder = new StringBuilder();
builder.append(a);
return builder.toString();
}

private static void swap(char[] a, int i, int j) {
char temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void main(String args[]) {
  
   //recursive anagram
   System.out.println("##########RECURSIVE##############");
   ArrayList<String> anagrams = recursiveAnagaram("Love");
   for(String s: anagrams)
       System.out.println(s);
   System.out.println("#############ITERATIVE###############");
   iterativeAnagram("Love");

}
}

/*

Output:

##########RECURSIVE##############
evoL
veoL
voeL
voLe
eovL
oevL
oveL
ovLe
eoLv
oeLv
oLev
oLve
evLo
veLo
vLeo
vLoe
eLvo
Levo
Lveo
Lvoe
eLov
Leov
Loev
Love
#############ITERATIVE###############
Love
oLve
vLoe
Lvoe
ovLe
voLe
eoLv
oeLv
Leov
eLov
oLev
Loev
Lveo
vLeo
eLvo
Levo
veLo
evLo
evoL
veoL
oevL
eovL
voeL
oveL

*/

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.