Question

How to generate all possible permutations and combinations of an array of chars in Java

Answer 1

import java.util.Arrays;
 
public class PermutationsAndCombinations {
 
    // Print an array of characters
    static void printArray(char[] arr) {
        for (char ch : arr) {
            System.out.print(ch + " ");
        }
        System.out.println();
    }
 
    // Print a subset of characters
    static void printSubset(char[] subset, int len) {
        for (int i = 0; i < len; i++) {
            System.out.print(subset[i] + " ");
        }
        System.out.println();
    }
 
    // Generate all permutations in lexicographic order
    static void generatePermutations(char[] arr) {
        Arrays.sort(arr); // Ensure lexicographic order
 
        do {
            printArray(arr);
        } while (nextPermutation(arr));
    }
 
    // Implementation of next_permutation for arrays
    static boolean nextPermutation(char[] arr) {
        int size = arr.length;
        int i = size - 2;
        while (i >= 0 && arr[i] >= arr[i + 1]) {
            i--;
        }
        if (i < 0) return false;
 
        int j = size - 1;
        while (arr[j] <= arr[i]) {
            j--;
        }
        swap(arr, i, j);
        reverse(arr, i + 1, size - 1);
        
        return true;
    }
 
    static void swap(char[] arr, int i, int j) {
        char tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
 
    static void reverse(char[] arr, int left, int right) {
        while (left < right) {
            swap(arr, left, right);
            left++;
            right--;
        }
    }
 
    // Generate all combinations using bitmask
    static void generateCombinations(char[] arr) {
        int size = arr.length;
        char[] subset = new char[size];
        for (int mask = 1; mask < (1 << size); mask++) {
            int len = 0;
            for (int i = 0; i < size; i++) {
                if ((mask & (1 << i)) != 0) {
                    subset[len++] = arr[i];
                }
            }
            printSubset(subset, len);
        }
    }
 
    public static void main(String[] args) {
        char[] arr = {'a', 'b', 'c'};
 
        System.out.println("All permutations:");
        generatePermutations(arr.clone()); 
 
        System.out.println("\nAll combinations:");
        generateCombinations(arr);
    }
}
 
 
 
/*
run:
 
All permutations:
a b c 
a c b 
b a c 
b c a 
c a b 
c b a 
 
All combinations:
a 
b 
a b 
c 
a c 
b c 
a b c 
 
*/

 

70+ SQL courses for beginners and professionals

Answer 2

public class PermutationsAndCombinations {
 
    // Swap two characters in an array
    static void swap(char[] arr, int i, int j) {
        char tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
 
    // Print array of chars
    static void printArray(char[] arr, int size) {
        for (int i = 0; i < size; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
 
    // Recursive function to generate permutations
    static void permute(char[] arr, int l, int r) {
        if (l == r) {
            printArray(arr, r + 1);
            return;
        }
        for (int i = l; i <= r; i++) {
            swap(arr, l, i);
            permute(arr, l + 1, r);
            swap(arr, l, i); // backtrack
        }
    }
 
    // Generate all combinations using bitmask
    static void generateCombinations(char[] arr, int size) {
        for (int mask = 1; mask < (1 << size); mask++) {
            for (int i = 0; i < size; i++) {
                if ((mask & (1 << i)) != 0) {
                    System.out.print(arr[i] + " ");
                }
            }
            System.out.println();
        }
    }
 
    public static void main(String[] args) {
        char[] input = {'a', 'b', 'c'};
        int size = input.length;
 
        System.out.println("All permutations:");
        permute(input, 0, size - 1);
 
        System.out.println("\nAll combinations:");
        generateCombinations(input, size);
    }
}
 
  
  
/*
run:
  
All permutations:
a b c 
a c b 
b a c 
b c a 
c b a 
c a b 
 
All combinations:
a 
b 
a b 
c 
a c 
b c 
a b c 
  
*/

 

70+ SQL courses for beginners and professionals