Program to find all permutations of a string in Java

In this Java tutorial, we will learn how to find all permutations of a string in Java. We will solve the problem using recursion. Recursion is a process where a function calls itself repeatedly. This function is called a recursive function.

Problem Statement

Given a string, we have to find all the permutations of that string. A permutation is a reordered arrangement of elements or characters of a string. For example, string “abc” have six permutations [“abc”, “acb”, “bac”, “bca”, “cab”, “cba”].

Input

We will be given a single string input.

Output

We have to print all the permutations of the given string in lexicographical order. A Lexicographical order means the order in which words or strings are arranged in a dictionary.

How to sort a String?

  • First, convert the string to a character array using toCharArray() method.
  • Sort the array using Arrays.sort() method.
  • Finally, obtain a string from the sorted array.
String str = "adcb";
char[] arr = str.toCharArray();
Arrays.sort(arr);
System.out.println(new String(arr));

Output:

abcd

String Functions used in the program

  • charAt(int index): It returns the character at the specified index.
  • substring(int begin, int end): It returns a part of the string from index begin to index end-1.
  • length(): It returns the length of a string.
  • Collections.sort(): It sorts the elements in the specified list of Collection. So, it is used to sort the ArrayList of strings.

 

Program to find all permutations of a string in Java

import java.util.Collections;
import java.util.Scanner;

public class permutations {
    public static void main(String[] args) {

        Scanner s = new Scanner(System.in);
        String str = s.next();

        ArrayList<String> answer = allPermutation(str);
        Collections.sort(answer);
        System.out.println(answer);

    }

    public static ArrayList<String> allPermutation(String str) {

        if (str.length()==0){
            ArrayList<String> baseResult= new ArrayList<>();
            baseResult.add("");
            return baseResult;
        }
        char ch = str.charAt(0);
        String rest = str.substring(1);

        ArrayList<String> recResult = allPermutation(rest);
        ArrayList<String> myResult = new ArrayList<>();
        for (int i = 0; i < recResult.size(); i++) {
            String s = recResult.get(i);
            for (int j = 0; j <= s.length(); j++) {
                String newString = s.substring(0, j) + ch + s.substring(j);
                myResult.add(newString);
            }
        }
        return myResult;
    }
}

Input:

adcb

Output:

[abcd, abdc, acbd, acdb, adbc, adcb, bacd, badc, bcad, bcda, bdac, bdca, cabd, cadb,
 cbad, cbda, cdab, cdba, dabc, dacb, dbac, dbca, dcab, dcba]

Explanation:

We pass the inputted string to the recursive allPermutations() function. We store the first character of the string in variable ch. And, the string rest contains the rest of the string which is passed to the recursive function. When the length of the string becomes 0, we create an empty ArrayList of string. This string returns to the recResult. Then, we iteratively obtain each string in recResult. Then, we place character ch at all positions in the string. We create an ArrayList myResult and add the resulting string to it. We return this myResult list each time. Finally, we get all the permutations of the string. We sort the final answer ArrayList using Collections.sort(). At last, we print the answer.

 

You can also read:

Leave a Reply

Your email address will not be published. Required fields are marked *