Anagrams Debunked (Java)

Firstly ,What are Anagrams?

Anagrams are basically just the rearrangements of the letters in a word (just like permutations).

An anagram of “Dormitory” is “Dirty room” and that of “The Morse Code” is “Here comes dots”. On the other hand , an  anagram of “Animosity” is “Is no Amity” and that of “dare” is “read”.

Permutations are rearrangements of variables which can be digits, letters, anything. Application of anagrams in computing largely involves the use of permutations from mathematics.(“Multiple anagramming” is a technique used to solve some kinds of cryptograms, such as a permutation cipher, a transportation cipher and the Jefferson Disk .) But it’s all good if you don’t have a pre-existing knowledge of permutations and combinations for this article.

For example , if the word is “abc”

Mathematically we have 6 number of different ways this word can be arranged. This is because, there being three variables (namely a, b and c) there are 3 factorial ways of forming permutations (i.e, 3 x 2 x 1  ways ). In the same way, there are 4 factorial ways ( 4 x 3 x 2 x 1 ) of arranging a word with four alphabets with no repetition of the alphabets. So, for “abc”,

The permutations are –

1. abc
2. acb
3. bac
4. bca
5. cab
6. cba

Note that we keep one letter constant , shuffle the remaining two (for a three letter word that is). For a 4 letter word keep one letter constant and shuffle the remaining three. Repetitions should not occur (please don’t mug this up, you’ll get how it is as you read along).

In 1. and 2. ‘a’ is constant ( ‘b’ and ‘c’ exchanged positions).

In 3. and 4. ‘b’ is constant , and ‘a’ & ‘c’ exchange positions and for 5. and 6. ‘c’ is constant and….. get the gist right?

Now a typical question asked in interviews is to write an algorithm for generating the anagrams of a word.

Go ahead give it a try.

Let’s see the code :

import java.util.*;
class Ana
{
public static void main(String[]args)
{
Scanner sc=new Scanner(System.in);
String s=sc.nextLine();
permutation(“”, s);
}
static void permutation(String a,String b)
{
if(b.length()==0)
System.out.println(a);
else
for(int i=0;i<b.length();i++)
permutation(a+b.charAt(i),b.substring(0,i)+b.substring(i+1,b.length()));
}
}

Now guys the part in bold is really important, let’s understand what it means.

At the starting, String ‘a’ is “” (null) and String ‘b’ is the string the user enters( let’s assume the user enters “klm”, for simplicity)

Some things to remember –

A string’s starting index is zero.

A function s.substring(i,j) returns the part of string s from index i to j-1

and substring(i) returns the part of a string from i till the end.

LETS GET STARTED!!!

static void permutation(String a,String b)
{
if(b.length()==0)
System.out.println(a);
else
for(int i=0;i<b.length();i++)
permutation(a+b.charAt(i),b.substring(0,i)+b.substring(i+1,b.length()));
}

(For those of you lazy to scroll on top)

‘a’ is null, and ‘b’ is “klm”

b’s length is non zero (precisely it is 3) so in the else part,

the loop from i=0 to  i<3  will be executed.

firstly, i=0.

and permutation (“” +b.charAt(0), b.substring(0,0) + b.substring(1,3)) will be called.

Note that (substring(0,0) is nothing)

i.e, permutation(“k”,”lm”) will be called. (more like a back to where we began cliché)

now ‘a’ is “k” and ‘b’ is “lm”.

b’s length is 2.

The loop is now from i=0 to i<2.

permutation(k+l, m)   (not gonna put quotes for everything. I presume you’d get that by now as a self exercise).

i.e, permutation (kl, m) function is called.

‘a’ is “kl” and ‘b’ is “m”.

b’s length is 1.

Again from i=0 till i<1 iteration runs.

permutation(kl+m,””).

i.e. permutation(klm,””)

(Note that in the previous cases, immediately after the first iteration of the loop is executed , the function permutation is called , so the function call takes place).

Now we see that ‘b’ is “” , at long last

so ‘a’ gets printed. i.e, “klm”

We’re not done just yet haha.

Now for the next round!!!

a=”kl”

and b=”m”

then ‘a’ becomes “k” and ‘b’ “lm”

and then ‘a’ is “km” and ‘b’ is “l”

(We CALL the same ol’ function again and again , if he was a guy , hey would’ve totally flipped out.)

now “kml” is printed

and the whole cycle gets repeated until all the other permutations are printed. It’s just like shuffling a bunch of cards over and over again.

Gave you somethin’ to show off , didn’t we?

Joke Of The Day: 

“Why do Java Programmers wear glasses ?”

“Because they don’t C# (see sharp)”

We are not responsible for any discrepancies.

We’ll be back with more interesting content.

Stay Tuned 😉