in this java application need to create an application which is able to produce
ID: 3838271 • Letter: I
Question
in this java application need to create an application which is able to produce all the anagrams for a word. An anagram is a rearranging of all the letters that make up the word. For example, consider the word “abcd”. It has 24 possible anagrams which are:
"abcd"
"bacd"
"cabd"
"dabc"
"abdc"
"badc"
"cadb"
"dacb"
"acbd"
"bcad"
"cbad"
"dbac"
"acdb"
"bcda"
"cbda"
“dbca"
"adbc"
"bdac"
"cdab"
“dcab"
"adcb"
"bdca"
“cdba”
"dcba"
From the “abcd” example, you should already be able to see a recursive pattern. Let’s take a look at the first column of the table above and see how recursion can generate it.
Starting with the word “abcd”, you would first take out the letter “a” leaving just the letters “bcd”. The letter “a” now becomes a prefix for all the possible anagrams to the new word “bcd”. You now recurse and do the same thing with the new word “bcd”. Take out the letter “b”, making your prefix now “ab” for all the possible anagrams to the new word “cd”. Recurse again, taking out the letter “c”, making your prefix now “abc” for all the possible anagrams to the new word “d”. Recurse again and this time you hit the base case because “d” has no anagrams other than itself. So print your prefix “abc” with your base case “d” and you get the value in row 1 column 1 of the table above.
But what about row 1 column 2? Well after hitting the base case “d” and printing the value in row 1 column 1, your recursive method calls unwind and you are back to the recursive method call where the prefix is “ab” and the word is “cd”. This time, however you remove the letter “d”, making you prefix now “abd” for all the possible anagrams to the new word “c”. Recurse again and you hit the base case again because “c” has no anagrams other than itself. So print your prefix “abd” with your base case “c” and you get the value in row 1 column 2 of the table above.
Now let’s look at row 1 column 3. After hitting the base case “c” and printing the value in row 1 column 2, your recursive method calls unwind some more and you are back to the recursive method call where the prefix is “a” and the word is “bcd”. You previously took the letter “b” out of “bcd” so you don’t want to do that again. Instead you want to move to the next letter and take the “c” out. Doing this, your prefix now becomes “ac” and the new word is “bd”. At this point I hope you can see how the recursive algorithm would continue until all the anagrams in column 1 are printed.
"abcd"
"bacd"
"cabd"
"dabc"
"abdc"
"badc"
"cadb"
"dacb"
"acbd"
"bcad"
"cbad"
"dbac"
"acdb"
"bcda"
"cbda"
“dbca"
"adbc"
"bdac"
"cdab"
“dcab"
"adcb"
"bdca"
“cdba”
"dcba"
Explanation / Answer
import java.util.*;
public class anagram
{
void input()throws Exception
{
Scanner sc = new Scanner(System.in);
System.out.print("Enter a word : ");
String s = sc.next();
System.out.println("The Anagrams are : ");
display("",s);
sc.close();
}
void display(String s1, String s2)
{
if(s2.length()<=1)
{
System.out.println(s1+s2);
}
else
{
for(int i=0; i<s2.length(); i++)
{
String a = s2.substring(i, i+1);
String b = s2.substring(0, i);
String c= s2.substring(i+1);
display(s1+a, b+c);
}
}
}
public static void main(String args[])throws Exception
{
anagram ob=new anagram();
ob.input();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.