Permutation/Anagram of string using recursion in java


In this core java programming tutorial we will write a program to find permutation/ combination/ anagram of String using recursion in java.



Example-
Permutations of inputString(ABC) are: [ACB, ABC, BCA, CBA, CAB, BAC]

Example-
Permutations of inputString(ABCD) are: [DABC, CADB, BCAD, DBAC, BACD, ABCD, ABDC, DCBA, ADCB, ADBC, CBDA, CBAD, DACB, ACBD, CDBA, CDAB, DCAB, ACDB, DBCA, BDAC, CABD, BADC, BCDA, BDCA]


In this post you will find two programs to find permutation/ combination/ anagram of String.

Program / Example1 - to find permutation/combination/anagram of String in java >
import java.util.HashSet;
import java.util.Set;

/** Copyright (c), AnkitMittal  JavaMadeSoEasy.com */
public class PemutationOfStringRecursion {
   public static void main(String...args) {
       String inputString = "XYZ";
       System.out.println("Permutations of inputString(" + inputString + ") are: " + findPermutation(inputString));
   }
  
   /**
    * method returns permutations of string.
    */
   public static Set<String> findPermutation(String inputString) {
       Set<String> set = new HashSet<String>();
       Set<String> set2;
       String stringWithoutFirstChar;
       char firstChar;
      
       if (inputString.length() == 0){
        set.add("");
        return set;
       }
       firstChar = inputString.charAt(0);
       stringWithoutFirstChar = inputString.substring(1);
       set2 = findPermutation(stringWithoutFirstChar);
      
       for (String s : set2) {
        for (int k=0; k<=s.length(); k++){
            set.add(insertCharacter(s, firstChar, k));
        }
       }
       return set;
   }
   public static String insertCharacter(String s, char ch, int i) {
       String begin = s.substring(0, i);
       String end = s.substring(i);
       return begin + ch + end;
   }
}
/*OUTPUT
Permutations of inputString(XYZ) are: [XYZ, XZY, YZX, ZYX, ZXY, YXZ]
*/



Program 2 - to find permutation/combination/anagram of String in java >
public class AnagramOrPermutation {
   static char[] ar = new char[100];
   static int length;
   public static void main(String[] args) {
          String inputString = "abc";
          length = inputString.length();
          ar=inputString.toCharArray();
          System.out.print("Anagram of inputString (" + inputString + ") are: " );
          anagram(length);
   }
         
   /*
   * Anagram method.
   */
   public static void anagram(int newLength) {
          if (newLength == 1) // return if newLength is 1.
                 return;
          for (int i = 0; i < newLength; i++){
                 anagram(newLength - 1); // recursively find the remaining anagrams.
                 if (newLength == 2)
                       displayWord();
                 rotate(newLength);
          }
   }
   /*
   * Rotate the string.
   */
   public static void rotate(int newLength) {
         
          char temp = ar[length - newLength];
          int i=0;
          for (i = (length - newLength) + 1; i < length; i++)
                 ar[i - 1] = ar[i];   //shift elements left.
          ar[i - 1] = temp;
   }
   /*
   * Method displays word.
   */
   public static void displayWord() {
          for (int i = 0; i < length; i++)
                 System.out.print(ar[i]);
          System.out.print(" ");
   }
}
/* output
Anagram of inputString (abc) are: abc acb bca bac cab cba
*/


Previous program                                                                  Next program



Having any doubt? or you you liked the tutorial! Please comment in below section.
Please express your love by liking JavaMadeSoEasy.com (JMSE) on facebook, following on google+ or Twitter.





RELATED LINKS>






No comments:

Post a Comment