# 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

## Leave a Reply

You must be logged in to post a comment.