Java Program to Print all Permutations of a String

Last Updated on June 20, 2024 by Abhishek Sharma

Generating all permutations of a string is a common problem in computer science, particularly in the fields of algorithms and combinatorics. A permutation of a string is a rearrangement of its characters into a new sequence. For example, the permutations of the string "ABC" are "ABC", "ACB", "BAC", "BCA", "CAB", and "CBA". Writing a Java program to print all permutations of a given string involves understanding recursive algorithms and backtracking techniques. This problem not only helps in grasping the fundamentals of recursion but also has practical applications in areas such as cryptography, game theory, and solving puzzles.

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
Writing a Java program to print all permutations of a string is an excellent way to understand and apply recursive algorithms. By exploring different ways to rearrange the characters of a string, you gain insights into the complexity and efficiency of various algorithmic approaches. This problem highlights the power of recursion and backtracking, providing a foundational understanding that can be applied to more complex problems in computer science. Whether for academic purposes, interview preparation, or practical applications, mastering string permutation generation is a valuable skill in a programmer’s toolkit.

Frequently Asked Questions about Java Program to Print all Permutations of a String

Below are some of the FAQs related to about Java Program to Print all Permutations of a String:

1. What is a permutation of a string?
Answer: A permutation of a string is a rearrangement of its characters into a different sequence. For example, the string "ABC" can be permuted to form "ACB", "BAC", "BCA", "CAB", and "CBA".

2. Why is it important to learn about string permutations?
Answer: Learning about string permutations is important because it helps in understanding recursive algorithms and backtracking. These techniques are fundamental in solving complex problems in computer science, such as combinatorial problems, puzzles, and optimization problems.

3. How does recursion help in generating permutations?
Answer: Recursion helps in generating permutations by breaking down the problem into smaller subproblems. It systematically explores all possible arrangements by swapping characters and recursively permuting the remaining characters.

4. What is backtracking, and how is it used in this context?
Answer: Backtracking is a technique for solving problems by exploring all possible solutions and abandoning those that fail to satisfy the constraints. In the context of string permutations, backtracking involves swapping characters and recursively generating permutations, then undoing the swaps (backtracking) to explore new possibilities.

5. What are the time and space complexities of generating all permutations?
Answer: The time complexity of generating all permutations of a string of length n is O(n!), as there are n! possible permutations. The space complexity is O(n) due to the recursion stack used for backtracking.

6. How can we handle permutations for strings with duplicate characters?
Answer: To handle permutations for strings with duplicate characters, you can use a set to track and avoid generating duplicate permutations. Alternatively, you can sort the string and skip duplicate characters during the swapping process.