ISourceCode

Make the frequent cases fast and the rare case correct

Algorithm to find all Permutations of a string

The problem can be solved by first trying to solve on paper for a 3 char string

For eg : a string XYZ can be chosen
we can set aside the first char and permute the remaining char. in this case
initial= X and permute(YZ) = YZ and ZY
Next we can insert X into the available position of this string
YZ — XYZ, YXZ, YZX
ZY — XZY, ZXY, ZYX

To achieve this we use Recursion.

import java.util.*;

public class StringPermutation {
	public static ArrayList<String> PermutationFinder(String s) {
	ArrayList<String> perm = new ArrayList<String>();
	if (s == null) { // error case
		return null;
	} else if (s.length() == 0) 
	{ 
		perm.add(""); // initial 
		return perm;
	}	
	char initial = s.charAt(0); // first character
	String rem = s.substring(1); // Full string without first character
	ArrayList<String> words = PermutationFinder(rem);
	for (String str : words) 
	{
		for (int i = 0; i <= str.length(); i++) 
		{
			perm.add(charinsert(str, initial, i));
		}
	}	
	return perm;
	}
	public static String charinsert(String str, char c, int j) {
	String begin = str.substring(0, j);
	String end = str.substring(j);
	return begin + c + end;
	}
	public static  void main(String[] args) {
    	String s = "CODE";
	ArrayList<String> value = PermutationFinder(s);
	System.out.println("\nThe Permutations are : \n" + value);
	}
}

OUTPUT:
laptop:~/code$ java StringPermutation

The Permutations are :
[CODE, OCDE, ODCE, ODEC, CDOE, DCOE, DOCE, DOEC, CDEO, DCEO, DECO, DEOC, COED, OCED, OECD, OEDC, CEOD, ECOD, EOCD, EODC, CEDO, ECDO, EDCO, EDOC]

Thanks for reading

3 responses to “Algorithm to find all Permutations of a string

  1. ujjaini April 24, 2012 at 7:49 pm

    very gd explanation

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: