Java Program to Print all Permutations of a String

Last Updated on May 17, 2023 by Prepbytes

The permutation of a string refers to all possible arrangements of its characters. For example, the permutations of the string "ABC" would be "ABC", "ACB", "BAC", "BCA", "CAB", and "CBA".

A string’s factorial length is always equal to the number of permutations possible.

Ways to Generate all Possible Permutations of String

As we progress through this post, we will discover two ways to produce every variant of a string in Java:

• Iterative approach
• Recursive Approach

Iterative Approach

ArrayList, which will initially include partial permutations, will be used to produce all of the string permutations in Java sequentially, and by employing it, we will ultimately obtain all useful arrangements.

In this program, an empty ArrayList has been generated and initialized using the string’s first character. The goal is to sequentially apply previously created partial permutations to each character of the given string. The current partial permutation will be removed from the ArrayList, and the following character from the given string will be inserted at all potential locations in the current partial permutation. The freshly created string will then be inserted into the ArrayList, and this procedure will be repeated until all potential permutations have been discovered.

Code Implementation

import java.io.*;
import java.util.*;

public class Main {

  public static void permutations(String str) {
    List<String> ans = new ArrayList<>(); 
    ans.add(String.valueOf(str.charAt(0)));

    for (int i = 1; i < str.length(); i++) {
      for (int j = ans.size() - 1; j >= 0; j--) {
        String temp = ans.remove(j);
        for (int k = 0; k <= temp.length(); k++) {
          ans.add(temp.substring(0, k) + str.charAt(i) + temp.substring(k));
        }
      }
    }

    System.out.println(ans);
  }

  public static void main(String[] args) {
    String str = "ABC";
    if (str.length() == 0 || str == null) {
      return;
    }
    permutations(str); 
  }
}

Output

[CAB, ACB, ABC, CBA, BCA, BAC]

Recursive Approach

The straightforward concept is to turn the string into a character array to produce its permutations because strings in Java are immutable and cannot be edited or updated. By replacing each of the string’s remaining characters with its initial position and utilising a recursive call to generate all possible combinations of the remaining characters, we may apply the idea of backtracking.

We shall use recursion or backtracking in our Java program to output every combination of a string that is conceivable. The solution method will receive the input string after being transformed into a character array using the toCharArray() function. To maintain track of the string’s arrangement, it is straightforward to swap the values of the character array with the character element provided as the index, and then run the solution method repeatedly to find the (index+1) value.

The current provided index value must equal (arr.length – 1) in order to satisfy the base condition, hence we will output the resulting array as one potential permutation of a text. We will swap once more to restore the initial values in the for loop following the recursive call in order to output every conceivable permutation. Backtracking allows the current character element to be utilized in other potential string configurations.

Code Implementation

import java.io.*;
import java.util.*;

public class Main {

    public static void swap(char[] arr, int idx, int idx2) {
    char temp = arr[idx];
    arr[idx] = arr[idx2];
    arr[idx2] = temp;
  }

  public static void solve(char[] arr, int idx) {
    if (idx == arr.length - 1) { 
      System.out.print(String.valueOf(arr) + " ");
    }

    for (int i = idx; i < arr.length; i++) {
      swap(arr, idx, i);
      solve(arr, idx + 1);
      swap(arr, idx, i);
    
    }
  }

  public static void main(String[] args) {
    
    String str = "ABC";
    if (str.length() == 0 || str == null) {
      return;
    }
    solve(str.toCharArray(), 0); 
  }
}

Output

ABC ACB BAC BCA CBA CAB

Conclusion
In conclusion, generating all permutations of a string involves finding all possible arrangements of its characters. This can be achieved using a recursive approach where one character is fixed at a time, and permutations are recursively generated for the remaining characters. The process continues until all characters have been fixed, resulting in a permutation. By swapping characters and recursively exploring different arrangements, all possible permutations can be obtained.

Frequently Asked Questions

Q1. How many permutations can be generated from a string of length N?
Ans. The number of permutations for a string of length N is N!.

Q2. Can duplicate characters be present in the string while generating permutations?
Ans. Yes, duplicate characters can be present. The algorithm will generate permutations taking into account all occurrences of each character.

Q3. How can I modify the algorithm to generate unique permutations if there are duplicate characters in the string?
Ans. To generate unique permutations when there are duplicate characters, you can modify the algorithm by checking for duplicates before swapping characters. You can maintain a set or a boolean array to keep track of characters that have already been fixed, and skip swapping if a duplicate character is encountered.

Q4. Are the permutations generated in any specific order?
Ans. The permutations are typically generated in lexicographic or dictionary order. However, depending on the implementation, the order may vary.

Q5. What is the time complexity of generating all permutations of a string?
Ans. The time complexity is O(N!), where N is the length of the string. Since there are N! permutations, the algorithm needs to perform operations for each permutation.