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 PermutationRecursion {
    static void permute(String str, int l, int r) {
        if (l == r)
            System.out.println(str);
        else {
            for (int i = l; i <= r; i++) {
                str = swap(str, l, i);
                permute(str, l + 1, r);
                str = swap(str, l, i);
            }
        }
    }

    static String swap(String a, int i, int j) {
        char[] charArray = a.toCharArray();
        char temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
        return String.valueOf(charArray);
    }

    public static void main(String[] args) {
        String str = "abc";
        permute(str, 0, str.length() - 1);
    }
}
            

Method 2: Using Next Permutation Algorithm

This method generates permutations using the next permutation algorithm.

import java.util.*;

public class NextPermutation {
    public static void main(String[] args) {
        String str = "abc";
        char[] arr = str.toCharArray();
        Arrays.sort(arr);
        str = new String(arr);
        do {
            System.out.println(str);
        } while ((str = nextPermutation(str)) != null);
    }

    public static String nextPermutation(String str) {
        char[] arr = str.toCharArray();
        int i = arr.length - 2;
        while (i >= 0 && arr[i] >= arr[i + 1]) i--;
        if (i < 0) return null;
        int j = arr.length - 1;
        while (arr[j] <= arr[i]) j--;
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        Arrays.sort(arr, i + 1, arr.length);
        return new String(arr);
    }
}
            

Method 3: Using Recursion with Sorting

This method generates and sorts permutations manually.

import java.util.*;

public class SortedPermutation {
    static void permuteSorted(String str, int l, int r) {
        if (l == r)
            System.out.println(str);
        else {
            for (int i = l; i <= r; i++) {
                str = swap(str, l, i);
                permuteSorted(str, l + 1, r);
                str = swap(str, l, i);
            }
        }
    }

    static String swap(String a, int i, int j) {
        char[] charArray = a.toCharArray();
        char temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
        return String.valueOf(charArray);
    }

    public static void main(String[] args) {
        String str = "abc";
        permuteSorted(str, 0, str.length() - 1);
    }
}