Question

How to generate all possible permutations and combinations of a list of chars in Java

Answer 1

import java.util.List;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;
 
public class PermutationsAndCombinations {
 
    // Print a list of characters
    static void printList(List<Character> list) {
        for (char ch : list) {
            System.out.print(ch + " ");
        }
        System.out.println();
    }
 
    // Generate all permutations in lexicographic order
    static void generatePermutations(List<Character> list) {
        Collections.sort(list); // Ensure lexicographic order
 
        do {
            printList(list);
        } while (nextPermutation(list));
    }
 
    // Implementation of next_permutation (like C++ STL)
    static boolean nextPermutation(List<Character> list) {
        int size = list.size();
        int i = size - 2;
         
        while (i >= 0 && list.get(i) >= list.get(i + 1)) {
            i--;
        }
         
        if (i < 0) return false;
 
        int j = size - 1;
        while (list.get(j) <= list.get(i)) {
            j--;
        }
         
        Collections.swap(list, i, j);
        Collections.reverse(list.subList(i + 1, size));
         
        return true;
    }
 
    // Generate all combinations using bitmask
    static void generateCombinations(List<Character> list) {
        int size = list.size();
         
        for (int mask = 1; mask < (1 << size); mask++) {
            List<Character> subset = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                if ((mask & (1 << i)) != 0) {
                    subset.add(list.get(i));
                }
            }
            printList(subset);
        }
    }
 
    public static void main(String[] args) {
        List<Character> list = new ArrayList<>(Arrays.asList('a', 'b', 'c'));
 
        System.out.println("All permutations:");
        generatePermutations(new ArrayList<>(list));
 
        System.out.println("\nAll combinations:");
        generateCombinations(list);
    }
}
 
 
 
/*
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