Java 實現多屬性分組的笛卡爾積組合生成與去重排序

問題場景

有一組 DTO 對象，每個對象包含 id 和 type。需要按 type 分組，從每組中選取一個 id 組成組合，輸出所有可能的組合，並要求排序、去重。

數據示例

輸入：
(100, "省份"), (200, "省份"),
(300, "業務"), (400, "業務"),
(500, "號碼")

輸出：
100,300,500
100,400,500
200,300,500
200,400,500

解決方案：遞歸回溯生成笛卡爾積

import java.util.*;

public class CartesianProduct {
    static class DTO { long id; String type; /* getter/setter */ }

    public static void main(String[] args) {
        List list = Arrays.asList(
            new DTO(100, "省份"), new DTO(200, "省份"),
            new DTO(300, "業務"), new DTO(400, "業務"),
            new DTO(500, "號碼")
        );

        // 1. 按 type 分組
        Map> groups = new LinkedHashMap<>();
        for (DTO d : list) {
            groups.computeIfAbsent(d.getType(), k -> new ArrayList<>()).add(d.getId());
        }

        // 2. 遞歸生成組合
        List results = new ArrayList<>();
        List types = new ArrayList<>(groups.keySet());
        backtrack(groups, types, 0, new StringBuilder(), results);

        // 3. 排序去重輸出
        results.stream().distinct().sorted().forEach(System.out::println);
    }

    static void backtrack(Map> groups, List types, int idx,
                          StringBuilder sb, List results) {
        if (idx == types.size()) {
            results.add(sb.toString());
            return;
        }
        for (Long id : groups.get(types.get(idx))) {
            int len = sb.length();
            if (len > 0) sb.append(",");
            sb.append(id);
            backtrack(groups, types, idx + 1, sb, results);
            sb.setLength(len);
        }
    }
}

關鍵點

• 使用 LinkedHashMap 保持分組順序穩定。
• 遞歸回溯構建組合字符串，避免創建大量中間對象。
• 最後利用 Stream API 完成去重與排序。