Java – Print all permutations of a String in Java | Code Factory

Donate : Link

Medium Blog : Link

Applications : Link

Given a String in, the task is to print all the permutations of in.

A permutation is an arrangement of all or part of a set of objects, with regard to the order of the arrangement.

Example:

• In: “AB”
• Out: AB, BA

• In: “ABC”
• Out: ABC, ACB, BAC, BCA, CAB, CBA

Please first try to do it yourself, then move to the solution.

Recursive Solution

Approach: Write a recursive function that prints every permutation of the given String.

package com.codeFactory;

/**
 * @author code.factory
 *
 */
public class Test {

	public static void main(String... strings) {
		func("ABC", "");
	}

	private static void func(String in, String out) {
		// If string is empty
		if (in.length() == 0) {
			System.out.print(out + " ");
			return;
		}

		for (int i = 0; i < in.length(); i++) {
			// ith character of str
			char ch = in.charAt(i);

			// Rest of the string after excluding the ith character
			String ros = in.substring(0, i) + in.substring(i + 1);

			// Recursive call
			func(ros, out + ch);
		}
	}
}

Output:

IN: AB
OUT: AB BA

IN: ABC
OUT: ABC ACB BAC BCA CAB CBA

/* Explanation */
func("AB", "")
	func("B", "A")
		func("", "AB") -> AB
	func("A", "B")
		func("", "BA") -> BA
	
func("ABC", "")
	func("BC", "A")
		func("C", "AB")
			func("", "ABC") -> ABC
		func("B", "AC")
			func("", "ACB") -> ACB
	func("AC", "B")
		func("C", "BA")
			func("", "BAC") -> BAC
		func("A", "BC")
			func("", "BCA") -> BCA
	func("AB", "C")
		func("B", "CA")
			func("", "CAB") -> CAB
		func("A", "CB")
			func("", "CBA") -> CBA

Static Solution

package com.test;

/**
 * @author code.factory
 *
 */
public class Test {

	public static void main(String[] args) {
		String str = "AB";
		int length = str.length();
		for(int i=0; i<length; i++) {
			for(int j=0; j<length; j++) {
				if(i == j) continue;
				System.out.println(str.charAt(i) + " " + str.charAt(j));
			}
		}
	}
}

Output:

A B
B A

. . . . .

package com.test;

/**
 * @author code.factory
 *
 */
public class Test {

	public static void main(String[] args) {
		String str = "ABC";
		int length = str.length();
		for(int i=0; i<length; i++) {
			for(int j=0; j<length; j++) {
				if(i == j) continue;
				for(int k=0; k<length; k++) {
					if(j == k || k == i) continue;
					System.out.println(str.charAt(i) + " " + str.charAt(j) + " " + str.charAt(k));
				}
			}
		}
	}
}

Output:

A B C
A C B
B A C
B C A
C A B
C B A

. . . . .

Dynamic Solution 1

package com.test;

/**
 * @author code.factory
 *
 */
public class Test {

	public static void main(String[] args) {
		String str = "AB";
		int length = str.length();
		for(int i=0; i<length; i++) {
			forLoop(str.charAt(i), length, str.substring(0, i) + str.substring(i+1));
		}
	}

	public static void forLoop(char ch, int length, String rem) {
		String r;
		for(int i=0; i<length-1; i++) {
			r = "";
			for(int j=i; j<length-1; j++) {
				r += rem.charAt(j);
			}
			for(int k=0; k<i; k++) {
				r += rem.charAt(k);
			}
			System.out.println(ch + r);
		}
	}
}

Output:

"AB"

AB
BA

"ABC"

ABC
ACB
BAC
BCA
CAB
CBA

. . . . .

Dynamic Solution 2 / Best Solution

package com.test;

/**
 * @author code.factory
 *
 */
public class Test {

	public static void main(String[] args) {
		String str = "ABC";
		int length = str.length();
		for(int i=0; i<length; i++) {
			forLoop(str.charAt(i), length, str.substring(0, i) + str.substring(i+1));
		}
	}

	public static void forLoop(char ch, int length, String rem) {
		String r;
		for(int i=0; i<length-1; i++) {
			r = "";
			r += rem.substring(i, length-1);
			r += rem.substring(0, i);
			System.out.println(ch + r);
		}
	}
}

Output:

Solution: Take 1st char and cyclic traverse remaining string.

"ABC"

ABC
ACB
BAC
BCA
CAB
CBA

"ABCD"

ABCD
ACDB
ADBC
BACD
BCDA
BDAC
CABD
CBDA
CDAB
DABC
DBCA
DCAB