Java Program to Compute all the permutations of the string

May 23, 2023

What are Strings?

A string is a sequence of characters. In Java, strings are used to represent text. You can use strings to store messages, names, and other kinds of text data.
Strings are usually represented as a series of characters enclosed in quotation marks. For example, in Java, you can create a string like this:
String s = “Hello World”;

In this Article, we will write a program to Compute all the permutations of the string.

Strings:

We can use the various methods of the String class to manipulate strings.
For example, you can use the length() method to get the length of a string, the substring() method to get a substring of a string, and the toUpperCase() method to convert a string to uppercase. You can also use the + operator or the concat() method to concatenate two strings.

What are Permutations of a String?

A permutation of a string is a rearrangement of the characters in the string to form a new word or phrase. For example, the permutations of the string “abc” include “abc”, “acb”, “bac”, “bca”, “cab”, and “cba”. There are a total of 3! (3 factorial) permutations of a string with 3 characters, which is 6.

Program to get all the permutation of a string :

Run

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

public class Main{
    
    // Function for returning permutations
    public static List permutations(String s){
        List permutations = new ArrayList<>();
        
        // Function calling to return permutations of a string
        permutationsHelper(s, "", permutations);
        return permutations;
    }
    
    // Helper function to take permutations
    private static void permutationsHelper(String s, String chosen, List permutations){
        
        // if the string is empty
        if (s.isEmpty()) {
            permutations.add(chosen);
        } else {
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                // choose
                chosen += c;
                s = s.substring(0, i) + s.substring(i + 1);
                // explore
                permutationsHelper(s, chosen, permutations);
                // un-choose
                s = s.substring(0, i) + c + s.substring(i);
                chosen = chosen.substring(0, chosen.length() - 1);
            }
        }
    }
    
    // Main function for input and output
    public static void main(String[] args){
        String s = "abc";
        
        // Function calling for permutations
        List permutations = permutations(s);
        System.out.println(permutations);
    }
}

Output:

[abc, acb, bac, bca, cab, cba]

Explanation :

In the above code, the permutations method uses recursion to find all possible permutations of the input string. It uses a helper method permutationsHelper which takes three arguments: the input string, a string that keeps track of the permutation being built, and a list of all permutations.

In the helper method, the base case is when the input string is empty, in that case, the permutation is added to the list. Else for each character in the string, it is added to the permutation being built, the character is removed from the input string and the helper method is called recursively with the modified input string and permutation. After the recursive call, the character is added back to the input string and removed from the permutation being built to backtrack.

In the main method, the permutations of the string ‘abc’ are calculated and printed.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others