Java 字符組合排序：圖論 DFS 與暴力枚舉雙解法實戰

題目描述

給定六個數字：1、2、2、3、4、5，要求輸出所有不重複的排列組合，並滿足兩個約束條件：

1. 數字 4 不能出現在第 3 位（索引 2）
2. 數字 3 與 5 不能相鄰

例如：512234、412345 等為合法排列。預期結果共 198 種。

解法一：圖論建模 + 深度優先搜索（DFS）

核心思想

將每個數字視為圖中的節點，構建鄰接矩陣表示可轉移關係：

• 預設所有不同索引的節點互連（g[i][j] = 1）
• 移除 3 與 5 之間的邊（g[3][5] = g[5][3] = 0），體現「不相鄰」約束
• 使用 TreeSet 自動去重與排序
• DFS 遞歸構建路徑，路徑長度達 6 時加入結果集

關鍵代碼實現

public class CharSequence {
    private String[] c = {"1","2","2","3","4","5"};
    private int n = c.length;
    private boolean[] visited = new boolean[n];
    private int[][] g = new int[n][n];
    private TreeSet<String> ts = new TreeSet<>();
    private String result = "";

    public CharSequence() {
        // 初始化鄰接矩陣
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = (i == j) ? 0 : 1;
            }
        }
        // 3 和 5 不能相鄰（索引 3 對應數字 3，索引 5 對應數字 5）
        g[3][5] = 0;
        g[5][3] = 0;
    }

    public void depthFirst(int index) {
        visited[index] = true;
        result += c[index];
        
        if (result.length() == n) {
            ts.add(result);
        } else {
            for (int i = 0; i < n; i++) {
                if (!visited[i] && g[index][i] == 1) {
                    depthFirst(i);
                }
            }
        }
        // 回溯
        result = result.substring(0, result.length() - 1);
        visited[index] = false;
    }

    public void graphicGet() {
        for (int i = 0; i < n; i++) {
            depthFirst(i);
        }
        int count = 0;
        for (String tmp : ts) {
            // 後處理：過濾 "4" 在第 3 位 的情況
            if (tmp.charAt(2) == '4') continue;  // 索引 2 即第 3 位
            if (tmp.contains("35") || tmp.contains("53")) continue;
            System.out.println(tmp);
            count++;
        }
        System.out.println("共計：" + count + "個");
    }
    // ... bruteForce 方法省略
}

圖論解法優缺點

解法二：暴力枚舉 + 剪枝優化

核心思想

遍歷從 122345 到 543222 的所有整數，將每個數字轉為字符串進行約束檢查：

1. 長度必須為 6
2. 第 3 位（索引 3）不能是 '4'
3. 不包含 "35" 或 "53"
4. 必須包含 1、3、4、5 各一次，2 兩次（通過查找兩個 2 的位置驗證）

關鍵代碼片段

public void bruteForce() {
    int count = 0;
    for (int i = 122345; i < 543222; i++) {
        String tmp = String.valueOf(i);
        if (tmp.length() != 6) continue;
        if (tmp.charAt(2) == '4') continue;  // 注意：題目說第3位，索引為2
        if (tmp.contains("35") || tmp.contains("53")) continue;
        
        // 驗證數字組成：1個1、2個2、1個3、1個4、1個5
        if (tmp.contains("1") && tmp.contains("3") && tmp.contains("4") && tmp.contains("5")) {
            int first2 = tmp.indexOf("2");
            if (first2 != -1 && first2 != tmp.length() - 1) {
                if (tmp.substring(first2 + 1).contains("2")) {
                    System.out.println(tmp);
                    count++;
                }
            }
        }
    }
    System.out.println("共計：" + count + "個");
}

兩種解法對比與啟示

總結

本題展示了同一問題的兩種截然不同思路：

• 圖論建模將約束轉化為拓撲結構，適合約束條件複雜、需頻繁變更的場景
• 暴力枚舉利用計算機高速運算優勢，配合剪枝條件快速過濾，適合數據範圍可控、一次性計算的場景

實際工程中，選擇哪種方案取決於問題規模、約束穩定性、維護成本的綜合權衡。掌握多種解題思維，才能在面對複雜業務邏輯時遊刃有餘。