Permutation of a given String

Objective: Given an String we need to generate all permutation of that string. e.g. if "abc" is an String we need to generate all possible permutation of this string. i.e. "abc", "acb", "bac", "bca", "cab", "cba" would be the possible permutation.

Approach: To understand the problem solving approach lets consider the following tree

In above tree we can see leaf of the tree represent the all permutations that we needed.

To describe the algorithm in functional way, if we want to generate permutation of "abc" with leading "a". We can have

'a' + permutation("bc")

Similarly, for leading "b" and "c", 

'b' + permutation("ac") and 'c' + permutation("ab")

Solution: Java Code

	public class GenerateAllPermutation {
	public static void main(String... arg) {
	Scanner scanner = new Scanner(System.in);
	String sequence = scanner.nextLine();
	generatePermutation("", sequence);
	}
	private static void generatePermutation(String prefix, String sequence) {
	if(sequence.length() == 0) System.out.println(prefix);
	for (int i = 0; i < sequence.length(); i++) {
	generatePermutation(prefix + sequence.charAt(i), sequence.substring(0, i) + sequence.substring(i+1));
	}
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub