Anagrams ( Creating Anagrams -Entered Words )

In our latest laboratory exercise, our professor threw down the gauntlet with a particularly challenging exercise: creating an anagram solver in Java. The task seemed straightforward at first glance, but as we delved deeper, it became clear that this was no ordinary coding assignment. We were tasked with developing a program that could take any given string and generate all possible anagrams, a feat that required not only a solid understanding of Java but also a keen eye for algorithmic efficiency. This exercise pushed us to think critically, optimize our code, and truly understand the intricacies of string manipulation in Java.

Source Code

import  java.io.*;

public class Anagrams
{
	public static void main(String[] args)throws IOException
	{
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		System.out.print("Enter a string:");
		String s = r.readLine();

		char[] text = new char[s.length()];
		for (int i = 0; i < s.length(); i++)
		{
			text[i] = s.charAt(i);
		}
		System.out.println("Here are all the anagrams of " + s);
		printAnagrams(text, 0);

	}

	public static void printAnagrams(char[] a, int i)
	{
		if (i == a.length-1)  {
			printArray(a);
		} else {
			for (int j=i; j< a.length; j++) {
				//swap a[i] with a[j]
				char c = a[i];
				a[i] = a[j];
				a[j] = c;
				printAnagrams(a, i+1);
				//swap back
				c = a[i];
				a[i] = a[j];
				a[j] = c;
			}
		}
	}

	static void printArray(char [] a)
	{
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i]);
		}
		System.out.println();
	}
}

Code Explanation

Let’s break down the code step-by-step:

1. Reading Input from the User

BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Enter a string:"); 
String s = r.readLine(); 

• BufferedReader is used to read input from the console. The user is prompted to enter a string, which is stored in the variable s.

2. Converting the String to a Character Array

char[] text = new char[s.length()]; 
for (int i = 0; i < s.length(); i++) {
    text[i] = s.charAt(i);
}

• The program creates a character array text of the same length as the input string s.
• Each character from s is then stored in the text array.

This array, text, holds each character individually, making it easier to swap characters as we generate anagrams.

3. Calling the printAnagrams Function

System.out.println("Here are all the anagrams of " + s);
printAnagrams(text, 0);

• The printAnagrams method is called with the character array text and an index 0 to start generating anagrams from the first character.

Core of the Program: printAnagrams Method

The printAnagrams method generates all anagrams by recursively swapping characters

public static void printAnagrams(char[] a, int i) {
    if (i == a.length - 1) printArray(a);
    else {
        for (int j = i; j < a.length; j++) {
            // Swap a[i] with a[j]
            char c = a[i];
            a[i] = a[j];
            a[j] = c;
            
            // Recursive call with the next index
            printAnagrams(a, i + 1);
            
            // Swap back to the original order
            c = a[i];
            a[i] = a[j];
            a[j] = c;
        }
    }
}

Explanation of printAnagrams:

        1. Base Case:

if (i == a.length - 1) printArray(a);

• If the index i reaches the end of the array, printArray is called to display the current arrangement as a potential anagram.

        2. Loop and Recursion:

for (int j = i; j < a.length; j++) { ... }

• The loop iterates from the current index i to the end of the array.
• In each iteration:
• Swap characters at positions i and j.
•     Recursive Call: printAnagrams(a, i + 1) generates anagrams of the rest of the array starting from the next index.
• Swap Back: After the recursive call, characters are swapped back to their original position to reset the array for the next iteration.

Utility Method: printArray

static void printArray(char[] a) {
    for (int i = 0; i < a.length; i++) System.out.print(a[i]);
    System.out.println();
}

• This method prints the current arrangement of the character array a, which represents one anagram of the original string.

How It Works: Example with “ABC”

Suppose the input string is "ABC". Here’s a simplified outline of what happens:

    1. Starting from the first character:

• Swap 'A' with 'A', call printAnagrams on "ABC"
• Swap 'A' with 'B', call printAnagrams on "BAC"
• Swap 'A' with 'C', call printAnagrams on "CBA"

    2. Each recursive call further swaps characters to explore all possible permutations.

Sample Output

For the input “ABC”, the program prints

ABC
ACB
BAC
BCA
CBA
CAB

Conclusion

This anagram generator is a great exercise in recursion and character manipulation. The code creates every possible rearrangement of characters by swapping and backtracking, a common technique for generating permutations. For more complex strings, this approach scales exponentially, illustrating the power (and limitations) of recursion in programming.