Printing all permutations

Question: Print all permutations of a String iteratively.

Related Tags:

Questions

  • Do we permute the repeated chars as well?

Assume that we permute the repeated chars as well, so that an input such as qqq should still return six results.

Recursive Solution

In a recursive solution, we create a method with two parameters - one storing the prefix, and one storing the rest of the string, s. The algorithm pseudocode is written below.

  1. If our string length is zero, print out the prefix.
  2. If our string length is not zero, recursively call the permutation algorithm appending a char at the prefix, and the original string without its front char removed.
static void permRecursive(String prefix, String s) {

	if (s.length() == 0) {
		System.out.println(prefix);
	} else {
		// for each char in String s, add to prefix 
		for (int i = 0; i < s.length(); i++) {
			permutations(prefix + s.charAt(i),
				s.substring(0,i) + s.substring(i+1));
		}
	}
}

Here's a stack trace of what's going on when you call permRecursive("", "ABCD");. The left side will be the prefix, and right side will be the String.

ABCD      // initial
A BCD 
AB CD 
ABC D 
ABCD      // No more s so print ABCD
-----
AB CD     // Step back to AB CD case, but now take the next char (D) into prefix
ABD C
ABDC      // Print ABDC
-----
A BCD     // Step back to A BCD case, appending the next char (C) into prefix
AC BD
ACB D
ACBD      // print ACBD
-----
AC BD     // Step back to AC BD case, appending the next char (D) into prefix
ACD B
ACDB      // print ACDB
-----
          // and so on..

Algorithm Implementation in Java

public class Permutations {
	public static void main(String[] args) {
		permRecursive("", "ABCD");
	}

	static void permRecursive(String prefix, String s) {

		if (s.length() == 0) {
			System.out.println(prefix);
		} else {
			// for each char in String s, add to prefix 
			for (int i = 0; i < s.length(); i++) {
				permutations(prefix + s.charAt(i),
					s.substring(0,i) + s.substring(i+1));
			}
		}
	}
}

Came up with a better solution or have a question? Comment below!