String Permutation


given abc, return abc, acb, bac, bca, cba, cab

consider it as tree, traverse tree recursively

Similar to the Number Permutation;

Idea: BFS, traverse level by level.

import java.util.*;

// take one character at a time and fix it at the first position
// use swap to put every character at the first position
// make recursive call to rest of the characters.
// use swap to revert the string back to its original for fo next iteration
class StringPermutations {
	private char[] arrA;

	private void permutation(char[] arrA, int left, int size) {
		int x;
		if(left == size) {
			for(int i = 0; i< arrA.length; i++) {
			System.out.print(" ");
		} else {
			for(x = left; x< size; x++) { // traverse each child
				swap(arrA, left, x);  // swap the position of characters
				permutation(arrA, left +1, size); // traverse deeper level
				swap(arrA, left, x);  // return the position of characters

	private void swap(char[] arrA, int i, int j) {
		char tmp = arrA[i];
		arrA[i] = arrA[j];
		arrA[j] = tmp;

	public static void main(String[] args) {
		String s = "abc";
		char[] arrCh = s.toCharArray();
		StringPermutations i = new StringPermutations();
		i.permutation(arrCh, 0 , arrCh.length);

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s