How to Generate all Permutations of a String in Java

The following Java program generates all the permutations of a string. It also eliminates any duplicate strings generated. This program can be used to generate anagrams. Note that the following program generates permutations in a case insensitive manner. Hence original case of the input string is not preserved in the permutations.

The following program uses a simple algorithm. We can find a subset of permutations by changing the first character of the string with each character in the string. Now for each of these permutations, we can find another subset by changing the second character of the string with each of the remaining characters. Now for each of these permutations, we can find another subset by changing the third character of the string with each of the remaining characters! We can continue this process until we run out of characters.

The above algorithm can be easily implemented using string operations and recursion. Each time we try to find the permutations of the remaining characters, we also pass the prefix (which includes previous characters and the current character). When we run out of characters, we know that the current prefix is a valid permutation. We simply add it to our unique set of permutations!

To ensure that we get only unique permutations, we are using the Set data structure (which doesn’t allow duplicate entries). 

How to Generate All Permutations of a String: Java Source code

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

// Java program to generate all permutations of a string
public class StringPermutationGenerator {

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

        System.out.print("Please enter a string: ");
        String string = scanner.nextLine();

        Set<String> permutations = generatePermutations(string);

        System.out.println("Here are the unique permutations of " + string);
        System.out.println(Arrays.toString(permutations.toArray()));

        scanner.close();
    }

    // Generate all permutations of a string in Java
    private static Set<String> generatePermutations(String input) {
        input = input.toLowerCase();
        Set<String> result = new HashSet<>();
        permutations("", input, result);
        return result;
    }

    // Recursive function for generating permutations
    // Each call contains the left side of a valid permutation and remaining characters
    private static void permutations(String prefix, String letters, Set<String> result) {
        if (letters.length() == 0) {
            result.add(prefix);
        } else {
            for (int i = 0; i < letters.length(); i++) {
                String letter = letters.substring(i, i + 1);
                String otherLetters = letters.substring(0, i) + letters.substring(i + 1);
                permutations(prefix + letter, otherLetters, result);
            }
        }
    }
}

Here is the sample output from the above program,

Please enter a string: sun
Here are the unique permutations of sun
[usn, nsu, snu, uns, sun, nus]

To change the above program to use case insensitive permutations, comment out the line containing input.toLowerCase.

Do you have a programming problem that you are unable to solve? Please send us your problem and we will publish the solution! Please email us.

Leave a Reply