Java 實現多組數據的排列組合算法

問題描述

給定多組字符數據，例如：

AB
C
DE
F

要求編寫 Java 算法，從每組中各取一個字符，生成所有可能的組合，如 ACDF、ACEF、BCDE、BCEF 等。

解決思路

這是一個典型的笛卡爾積問題，可以使用遞歸回溯的方式實現。將每組數據存放在二維字符數組中，遞歸遍歷每一組，將當前選擇的字符拼接到結果字符串中，當處理完所有組別時，將結果保存。

代碼實現

public class CombinationGenerator {
    private static int size = 0;

    public static void main(String[] args) {
        char[][] data = {{'A', 'B'}, {'C'}, {'D', 'E'}, {'F'}};
        
        // 計算總組合數
        int total = 1;
        for (char[] group : data) {
            total *= group.length;
        }
        
        String[] result = new String[total];
        generateCombinations(data, 0, "", result);
        
        // 輸出結果
        for (String s : result) {
            System.out.println(s);
        }
    }

    private static void generateCombinations(char[][] data, int index, String current, String[] result) {
        if (index == data.length) {
            result[size++] = current;
            return;
        }
        for (char c : data[index]) {
            generateCombinations(data, index + 1, current + c, result);
        }
    }
}

關鍵點解析

• 遞歸終止條件：當 index == data.length 時，說明已從每組中選取一個字符，將組合存入結果數組。
• 狀態傳遞：通過參數 current 累加已選字符，避免使用全局變量。
• 時間複雜度：O(N₁ × N₂ × … × Nₖ)，即所有組合的總數。

運行結果

ACDF
ACEF
BCDF
BCEF

該算法靈活通用，可處理任意組數、任意長度的字符組合生成需求。