Java Program to Compute All Permutations of a String

In this Java program, we will learn to print all possible permutations of a string. In Java, you can compute all the permutations of a string by using a recursive algorithm that generates all possible permutations of a substring of the original string.

Here is an example of how you can compute all the permutations of a string in Java.

---

Java Program to Compute All Permutations of a String Using Recursion

import java.util.ArrayList;
import java.util.List;

public class PermutationExample {

  public static List<String> permute(String str) {
    List<String> permutations = new ArrayList<>();
    permute("", str, permutations);
    return permutations;
  }

  private static void permute(String prefix, String str, 
      List<String> permutations) {
    int n = str.length();
    if (n == 0) {
      permutations.add(prefix);
    } else {
      for (int i = 0; i < n; i++) {
        permute(prefix + str.charAt(i), str.substring(0, i) + 
           str.substring(i + 1, n), permutations);
      }
    }
  }

  public static void main(String[] args) {
    String str = "xyz";
    System.out.println(permute(str));
  }
}

Output

[xyz, xzy, yxz, yzx, zxy, zyx]

In this example, the main method first calls the permute method and pass it the string "xyz". The permute method takes three arguments:

• A prefix string, which is initially empty and will be used to store the permutation currently being generated.


• The input str string, which is the string whose permutations are to be computed.


• A list of strings, permutations, which will be used to store all the permutations of the input string.

The permute method first checks if the input string str is empty, if it is, it adds the prefix to the permutations list. If the input string is not empty, it uses a for loop to iterate over the characters in the string and for each character, it calls the permute method again with the following arguments:

• A new prefix, which is the current prefix concatenated with the current character.


• A new input string, which is the original input string with the current character removed from it.


• The same permutations list.

This way, the function recursively calls itself for every possible substring of the original string, generating all possible permutations of the input string.

After generating all permutations, the permute method returns the permutations list which contains all the permutations of the input string. The main method then prints the list of permutations to the console.

It's important to note that this algorithm has a time complexity of O(n!) where n is the length of the input string, which can be quite large for longer strings.

---

Previous
Java Program to Display the Name of OS

Next
Java Program to Iterate Over Enum Values