List all permutations of a given string in dictionary order in Java

Understanding String Permutations

String permutations refer to all possible arrangements of characters in a given string. The dictionary order means sorting them lexicographically.

We will explore three different methods to list all permutations of a given string in Java.

Method 1: Using Recursion

This method generates permutations recursively by swapping characters.

import java.util.*;

public class PermutationsRecursion {
    static void permute(String str, String answer) {
        if (str.length() == 0) {
            System.out.println(answer);
            return;
        }
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            String rest = str.substring(0, i) + str.substring(i + 1);
            permute(rest, answer + ch);
        }
    }
    public static void main(String[] args) {
        String str = "abc";
        permute(str, "");
    }
}
            

Method 2: Using Next Permutation

This method generates permutations in lexicographical order.

import java.util.*;

public class NextPermutation {
    public static void main(String[] args) {
        String str = "abc";
        char[] arr = str.toCharArray();
        Arrays.sort(arr);
        do {
            System.out.println(new String(arr));
        } while (nextPermutation(arr));
    }
    private static boolean nextPermutation(char[] arr) {
        int i = arr.length - 2;
        while (i >= 0 && arr[i] >= arr[i + 1]) i--;
        if (i < 0) return false;
        int j = arr.length - 1;
        while (arr[j] <= arr[i]) j--;
        swap(arr, i, j);
        reverse(arr, i + 1, arr.length - 1);
        return true;
    }
    private static void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    private static void reverse(char[] arr, int i, int j) {
        while (i < j) swap(arr, i++, j--);
    }
}
            

Method 3: Using Collections

This method sorts the string and uses Java's next permutation approach.

import java.util.*;

public class CollectionsPermutation {
    public static void main(String[] args) {
        String str = "abc";
        List permutations = new ArrayList<>();
        generatePermutations("", str, permutations);
        Collections.sort(permutations);
        for (String perm : permutations) {
            System.out.println(perm);
        }
    }
    private static void generatePermutations(String prefix, String str, List permutations) {
        if (str.isEmpty()) {
            permutations.add(prefix);
        } else {
            for (int i = 0; i < str.length(); i++) {
                generatePermutations(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1), permutations);
            }
        }
    }
}