Java Program to Print all Permutations of a String

Problem: Write a Java program to print all permutations of a string

Example:

Input:  lol
Output: lol, llo, oll

Input:  hat
Output: hat, aht, ath, hta, tha, tah 

The best method to solve this problem is using recursion because a part of the string is itself a string that can be rearranged to form various pemutations.

Example:

l [ol, lo]
o [ll]

To form all possible permutations of a given string, we extract characters from the string one by one (using a loop) and append them to another string (perm).

We then recursively repeat the above process for the remaining characters in the string until there is none left.

When no characters are left in the string, we output the formed permutation depending on whether it is unique (has not occurred previously).

Here is the Java program, that implements the logic:

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

class Main {
  //list to store the permutaions
  static List<String> output = new ArrayList<>();

  public static void main(String[] args) {
    Scanner in = new  Scanner(System.in);

    //Input a string
    System.out.print("Enter a string: ");
    String str = in.next();

    /*
      *call the permutation method with empty string as 1st
      *and input string as the 2nd parameter
    */
    System.out.print("All Permutations: ");
    permutation("", str);
  }

  public static void permutation(String perm, String word){
    //base condition: word is empty
    if(word.isEmpty()){
      //print only if a new permutation is found
      if(!output.contains(perm)){
        System.out.print(perm+" ");
        output.add(perm);
      }
    }

    //Loop
    for(int i=0; i<word.length(); i++){
      //split: remove the character at i from the word and append to the perm
      String w = word.substring(0,i) + word.substring(i+1,word.length());
      String p = perm + word.charAt(i);

      //recursive call
      permutation(p, w);
    }
    
  }
}

Output:

Enter a string: lol
All Permutations: lol llo oll

Enter a string: 123
All Permutations: 123 132 213 231 312 321

In our program, we store all the permutations in a list to print only the unique ones.

We can also input a number to print all its permutations using the above program, as it will be treated as a string.

All permutations of a string can also be called anagrams, so the above program is also the program to print all anagrams of a string.