WAP to Find all the Permutations of a String

Find all the Permutations of a String: The given Java program generates all possible permutations of a given input string and prints them comma-separated. For the input string “abc,” the output will be “abc,acb,bca,bac,cab,cba,” representing all the unique combinations of the characters in the input string.

Find all the Permutations of a String

package com.softwaretestingo.interviewprograms;
public class InterviewPrograms43 
{
	/*
	 * Input = “abc”; 
	 * Output = abc,acb,bca,bac,cab,cba,
	 */
	public static void main(String[] args) 
	{
		String str = "abc";
		int n = str.length();
		merge(str, 0, n - 1);
	}
	private static void merge(String str, int lb, int ub)
	{
		if (lb == ub)
			System.out.print(str+",");
		else 
		{
			for (int i = lb; i <= ub; i++) 
			{
				str = swap(str, lb, i);
				merge(str, lb + 1, ub);
				str = swap(str, lb, i);
			}
		}
	}
	public static String swap(String a, int i, int j)
	{
		char temp;
		char[] ch = a.toCharArray();
		temp = ch[i];
		ch[i] = ch[j];
		ch[j] = temp;
		return String.valueOf(ch);
	}
}

Output

abc,acb,bac,bca,cba,cab,

Here’s a step-by-step explanation of the program:

1. Define the main method:
   • The program starts executing from the main method.
2. Initialize the input string:
   • The input string str is initialized with the value “abc.”
3. Calculate the length of the string:
   • The length of the string n is calculated using the length method.
4. Call the merge method:
   • The merge method is called to generate all the permutations of the input string.
   • The method is called with the input string str, and the lower bound (lb) is set to 0, and the upper bound (ub) is set to n – 1.
5. Implement the merge method:
   • The merge method uses recursion to generate all permutations of the input string.
   • If the lower bound (lb) is equal to the upper bound (ub), it means that a single permutation is obtained, and it is printed followed by a comma.
   • Otherwise, a loop runs from the lower bound (lb) to the upper bound (ub).
   • In each iteration, the swap method is called to swap the characters at the lb and i indices of the string str.
   • Then, the merge method is recursively called with the updated string and an incremented lower bound (lb + 1).
   • After the recursion, the swap method is called again to restore the original order of characters.
6. Implement the swap method:
   • The swap method takes a string a and two indices i and j as parameters.
   • It converts the string a to a character array ch.
   • Then, it swaps the characters at indices i and j using a temporary variable temp.
   • Finally, it returns the updated string after the swap.

The program uses a recursive approach to generate all the possible permutations of the input string “abc” and prints them comma-separated. The output will be “abc,acb,bca,bac,cab,cba,” representing all the unique combinations of the characters in the input string.