String Permutation

Reference: http://algorithms.tutorialhorizon.com/print-all-the-permutations-of-a-string/

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(arrA[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);
	}
}
Advertisements

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