Find all anagrams of a word in Java

Posted By: Achchuthan Yogarajah - 10:22 PM

Share

& Comment

Finding an algorithm to answer this question may seem challenging because finding all the different permutations of a string is something that you just do naturally without really thinking about it. But, try to figure out what algorithm you are implicitly using in your mind whenever you write down all the different permutations of a string. Let’s use the word “dogs” as an example and see what different permutations we get. Here is what comes up when we list out all the possible permutations of the letters in “dogs”: 

 dogs sgod gsod ogsd 
dosg sgdo gsdo ogds 
dsgo sdgo gdso osdg 
dsog sdog gdos osgd 
dgso sodg gods odgs 
dgos sogd gosd odsg


So, when we came up with the permutations of “dogs” above, how did we do it? What were we implicitly thinking? Well, it looks like what we did in each column was choose one letter to start with, and then we found all the possible combinations for the string beginning with that letter. And once we picked a letter in the 2nd position, we then found all the possible combinations that begin with that 2 letter sequence before we changed any of the letters in the first 2 positions. So, basically what we did was choose a letter and then peformed the permutation process starting at the next position to the right before we come back and change the character on the left.

Finding the permutations with recursion

 Our description of the process that we followed sounds a lot like something that could be solved with recursion. How can we change our description so that it’s easier to write out in a recursive method? Let’s phrase it like this: In order to find all possible combinations for a given string, then start at a position x, then find and place all possible letters in position x. Every time we put a new letter in position x, we should then find all the possible combinations at position x+1 – this would be the recursive call that we make. How do we know when to print out a string? Well, when we are at a position x that is greater than the number of letters in the input string, then we know that we have found one valid combination/permutation of the string and then we can print it out and return to changing letters at positions less than x. This would be our base case – remember that we always must have a recursive case and a base case when using recursion. 

 Which letters can we use in a given position? 

 Another big part of this problem is figuring out which letters we can put in a given position. Using our sample string “dogs”, lets say that we are going through all the permutations where the first 2 letters are “gs”. Then, it should be clear that the letters in the 3rd or 4th position can only be either “d” or “o”, because “g” and “s” were already used. As part of our algorithm, we have to know which letters can be used in a given position – because we can’t reuse the letters that were used in the earlier positions. And in order to do this we can simply have an array of Boolean values that correspond to the positions of the letters in the input string – so if a certain character from the input string has already been used, then it’s position in the array would be set to “true”.

Java version of this program :

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author ACHCHUTHAN
 */
public class Anagram {

    public static char[] charArray;

    public Anagram(String word) {
        charArray = word.toCharArray();
        doAnagram(charArray.length);
    }

    public void changeOrder(int newsize) {
        int j;
        int pointAt = charArray.length - newsize;
        char temp = charArray[pointAt];

        for (j = pointAt + 1; j < charArray.length; j++) {
            charArray[j - 1] = charArray[j];
        }

        charArray[j - 1] = temp;

    }

    public void doAnagram(int newsize) {
        if (newsize == 1) {
            return;
        }
        for (int i = 0; i < newsize; i++) {
            doAnagram(newsize - 1);
            if (newsize == 2) {
                display();
            }
            changeOrder(newsize);
        }
    }

    public void display() {
        for (int i = 0; i < charArray.length; i++) {
            System.out.print(charArray[i]);
        }
        System.out.println();
    }

    public static void main(String args[]) {
        Anagram test1 = new Anagram("Love");



    }
}

output of this program

run:
Love
Loev
Lveo
Lvoe
Leov
Levo
oveL
ovLe
oeLv
oevL
oLve
oLev
veLo
veoL
vLoe
vLeo
voeL
voLe
eLov
eLvo
eovL
eoLv
evLo
evoL
BUILD SUCCESSFUL (total time: 1 second)

About Achchuthan Yogarajah

I’m passionate about Web Development and Programming and I go to extreme efforts to meet my passion. I’m a believer of learning the fundamentals first. I try to understand everything little bit more than the average.

0 comments :

Post a Comment

Thank you for vising Java90.blogspot.com

Copyright © 2016 Java Examples ACHCHUTHAN.ORG. Designed by Templateism .