Java code to find all permutations of a String using recursion | Printing all combinations of a string with example

A permutation is an arrangement of set of objects in a particular order. The number of permutations of n objects is n*(n – 1)*(n – 2)*…3*2*1 that means n factorial (n!)

Examples :

1. Permutation of given Set {4,5,6} -> Set has 3 objects, so no of permutations are 3! = 6 which is as follows
{ 456, 465 ,546 ,564, 645 ,654}

2. Permutation of given set {T,E,C,H) -> It has 4 objects, no of permutations are 4! = 24
{TECH, TEHC,TCEH,TCHE,THEC,THCE,ETCH, ETHC, ECTH,ECHT,EHTC,EHCT,CTEH, CTHE, CETH ,CEHT, CHTE, CHET,HTEC,HTCE,HETC, HECT,HCTE,HCET }

The following code finds the all permutations of a given string through command prompt using recursion. We have two methods to find all permutations.

Steps to find all permutations of n objects:

Let us assume that the objects are characters here.  for  eg. {a,b,c}

1. Separate the first character  from the rest of the characters.

2. Get all permutations of the rest of the characters.

3. Insert the first character in all possible positions of the rest of the characters.

4. Proceed Step 1 until the rest of characters becomes 1.

This is done using recursion */


package com.javaonline;

import java.util.ArrayList;

public class Permutation {

//Main method
 public static void main(String args[]) {

 if (args.length!=1)
 {
 System.out.println("invalid input");
 System.exit(0);

 }

 String inputStr=args[0];
 System.out.println("Given Input :" + inputStr+"\n"); 

 ArrayList <String> result1 =new ArrayList<String>();

 System.out.println("Using Method I\n");

 findPermutation("", inputStr, result1);

 System.out.println(result1);

 System.out.println("The number of permutations are " + result1.size() + " is equal to "+inputStr.length() + "! = " + fact(inputStr.length()) );

 System.out.println("\nUsing Method II\n");

 ArrayList<String> result2= Permutations(inputStr);

 System.out.println(result2);

 System.out.println("The number of permutations are " + result2.size() + " is equal to "+inputStr.length() + "! = " + fact(inputStr.length()) );

 }

//Method II

public static ArrayList<String> Permutations(String inputStr) {

 ArrayList<String> resultArray = new ArrayList<String>() ;

 if (inputStr.length() == 1)
 {
 resultArray.add(inputStr);
 return resultArray;
 }
 else {
 // For separating the first character from the rest of the char
 char first = inputStr.charAt(0);
 String rest = inputStr.substring(1);
 // get all permutations of the rest of the characters
 ArrayList<String> tempResultArray = Permutations(rest); // using Recursion
 // for each permutation,
 for (String permutation : tempResultArray) {
 ArrayList tempPermut= insertFirstchar(first, permutation);
 resultArray.addAll(tempPermut);
 }
 return resultArray;
 }
}

 // Insert the first character in all possible positions of the rest of the charaters.

private static ArrayList<String> insertFirstchar(char first, String rest) {
 ArrayList<String> restResult = new ArrayList<String>();
 for (int i = 0; i <= rest.length(); i++)
 {
 String mergeStr = rest.substring(0, i) + first + rest.substring(i);
 restResult.add(mergeStr);
 }
 return restResult;
}

//Method I

 public static void findPermutation(String first, String rest, ArrayList<String> resultArray) {
 if (rest.length() <= 1)
 resultArray.add(first+rest);

 else
 for (int i = 0; i < rest.length(); i++) {
 try {
 String newString = rest.substring(0, i) + rest.substring(i + 1);
 findPermutation(first + rest.charAt(i), newString, resultArray);

 } catch (Exception e) {
 e.printStackTrace();
 }
 }

 }

 //For finding factorial

 public static int fact(int n)
 {
 int factorial=1;

 if (n<=1) return n;
 else
 factorial= n* fact (n-1);

 return factorial;

 }

}

In the above code, the outputs are captured in a arraylist and displayed. The number of elements in the arraylist is equal to the number of permutations of the given input. You can also capture in a Set when you give unique objects as input so that you can ensure no duplicate permutations are generated.

Running the above program will result the following

Permutation output1

Permutation output2

You may also like

Leave a Reply

2 Comments on "Java code to find all permutations of a String using recursion | Printing all combinations of a string with example"


Guest
Factorial Fairy
1 year 6 months ago

Just a heads up that you wrote 4! = 16. Saw that you have 24 permutations so I’m guessing you had a little typing error.