Wednesday 23 September 2015

Java program to compute all permutation of String


To understand this solution first understand the concept of recursion.
So here lets assume a given string S represented by S1,S2,S2....,Sn.
To permute String S ,we can select the first character S1,permute the remainder of string to get a new list.Then with a new list we can push S1 into each possible positions.

import java.util.ArrayList;  
 import java.util.List;  
 /**  
  *   
  */  
 /**  
  * @author Dixit  
  *   
  */  
 public class StringPermutation {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           List<String> listOfAllPermutatuons=getPerms("abc");  
           for(String s:listOfAllPermutatuons)  
           {  
                System.out.println(s);  
           }  
      }  
      public static ArrayList<String> getPerms(String s) {  
           ArrayList<String> permutations = new ArrayList<String>();  
           if (s == null) {   
                return null;  
           } else if (s.length() == 0) {   
                permutations.add("");  
                return permutations;  
           }  
           char first = s.charAt(0); // get the first character  
           String remainder = s.substring(1); // remove the first character  
           ArrayList<String> words = getPerms(remainder);  
           for (String word : words) {  
                for (int j = 0; j <= word.length(); j++) {  
                     permutations.add(insertCharAt(word, first, j));  
                }  
           }  
           return permutations;  
      }  
      public static String insertCharAt(String word, char c, int i) {  
           String start = word.substring(0, i);  
           String end = word.substring(i);  
           return start + c + end;  
      }  
 }  



Output  
 abc  
 bac  
 bca  
 acb  
 cab  
 cba  


NOTE:- To understand this solution clearly,try to put a debug point and go through each line.

Enjoy Programming

No comments:

Post a Comment