Print all possible permutations of a String – Recursive Method

Performance analysis of String Permutations Programs

Till now I have discussed different ways of creating String Permutations and also discussed about the performance advantage of one program over the other. Now lets see how both of those programs differ from each other in respect of consuming time. With this you will be able to see how much time your program consume and you can do this for any of your program.

Now we will check these programs by taking same String with repeating character multiple time and will note the time consumed at different String length.

Lets again have a look at both the programs. This time we will focus on time consumed by them and hence I have removed java.util.Set and printing stuff.

So the two program changes to….

Program 1

import java.util.Calendar;

public class StringPermutations {
	public static void main(String[] args) {

		StringBuilder string = new StringBuilder("aaaaaaaaaaa"); // 'a' repeating 11 times

		System.out.println("starting time in millis - "+ Calendar.getInstance().getTimeInMillis());
		permutation(string, 0, string.length());
		System.out.println("ending time in millis - "+ Calendar.getInstance().getTimeInMillis());
	}

	static void exchange(StringBuilder input, int i, int j) {
		String temp;
		temp = input.substring(i, i + 1);
		input.replace(i, i + 1, input.substring(j, j + 1));
		input.replace(j, j + 1, temp);
	}

	static void permutation(StringBuilder input, int i, int length) {
		if (i == length - 1) {
			//new String created
		} else {
			for (int j = i; j < length; ++j) {
				exchange(input, i, j);
				permutation(input, i + 1, length);
				exchange(input, i, j);
			}
		}
	}
}

Output:-

starting time in millis - 1411224293111
ending time in millis -   1411224320303

In above example when we take a String of a’s repeating 1 times this program took nearly 27 seconds. Now lets see for another program.

Program 2

package codingeekStringTutorials;

import java.util.Calendar;

public class StringPermutations {
	public static void main(String[] args) {

		String string = new String("aaaaaaaaaaa"); // 'a' repeating 11 times

		System.out.println("starting time in millis - "+ Calendar.getInstance().getTimeInMillis());
		permutation(string, "");
		System.out.println("ending time in millis - "+ Calendar.getInstance().getTimeInMillis());
	}

	private static void permutation(String input, String sofar) {
		if (input.equals("")) {
			// new String Generated
		}
		for (int i = 0; i < input.length(); i++) {
			char c = input.charAt(i);
			if (input.indexOf(c, i + 1) != -1)
				continue;
			permutation(input.substring(0, i) + input.substring(i + 1), sofar + c);
		}
	}
}

Output:-
starting time in millis - 1411224953895
ending time in millis - 1411224953896

You can see the difference now as this program took only 1 millisecond to process the complete String and Generate its permutations( which is obviously very less than 27 seconds).

See this analytics when we perform this test on different size of String all containing single character multiple times like ‘aaaaa’, ‘aaaaaa’, ‘aaaaaaa’ etc.

Recommended -