To find the all permutations of a string we can use dynamic programming. In order to do that lets try to find permutation for 1,2 and 3 character string and find out if we can find any pattern that can be applied on ‘n’ characters.
Permutation('a') : a
For two character string ‘ab’
Permutation('ab') : ab,ba
For three character string ‘abc’
Permutation('abc') : abc,acb,bac,bca,cab,cba
In above examples if we try to find pattern, the Permutation(‘a’) and Permutation(‘ab’) is constant. But Permutation(‘abc’) can be formed using Permutation(‘ab’) and ‘c’. i.e., we apply c at every possible place in
Permutation('ab') = {ab,ba}
Hence we can find
cab,acb,abc cba,bca,bac
Hence final result
Permuatation('abc') : [cab,acb,abc,cba,bca,bac]
Hence same can applied for n character string where char[n] can be placed into Permutation of (n-1) characters.
Following is a simple and quick implementation in Java
package com.premute; import java.util.HashSet; import java.util.Set; public class StringPermuter { public static void main(String[] args) { StringPermuter permuter = new StringPermuter(); String[] perms = permuter.permute("abc"); if(perms != null) { System.out.println("Total Permutaions : "+perms.length); if(perms.length >0) { for(String s:perms) System.out.println(s); } } } public String[] permute(String string) { if(string!= null) { char[] chars= string.toCharArray(); if(chars.length == 0) return null; else if(chars.length == 1) { //Permutation for one char String[] strs = new String[1]; strs[0] = new StringBuilder().append(chars[0]).toString(); return strs; } else if (chars.length == 2) { //Permutation for two chars String[] strings = new String[2]; strings[0] = new StringBuilder().append(chars[0]).append(chars[1]).toString(); strings[1] = new StringBuilder().append(chars[1]).append(chars[0]).toString(); return strings; } else { Set set = new HashSet(); //Find permuation of n-1 chars String[] permutations = permute(string.substring(0, chars.length-1)); //nth char char ch = chars[chars.length-1]; //Place nth char in all places in Permutation(n-1) for(String str : permutations) { char[] chrs = str.toCharArray(); int x=0,y=0; StringBuilder newString = null; while(x<=chrs.length) { newString = new StringBuilder(); y=0; while(y<x) { newString.append(chrs[y]); y++; } newString.append(ch); while(y<chars.length-1) { newString.append(chrs[y]); y++; } set.add(newString.toString()); x++; } } return set.toArray(new String[0]); } } return null; } }
Output for
String[] perms = permuter.permute(“a”);
Total Permutaions : 1 a
String[] perms = permuter.permute(“ab”);
Total Permutaions : 2 ab ba
String[] perms = permuter.permute(“abc”);
Total Permutaions : 6 cab abc cba bac bca acb
Note : This code has potential for improvements.