萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

Java 排列組合演算法大全:位元狀態、遞歸回溯、動態規劃三大經典解法

問題定義

  • **排列** — 有序選擇:從 n 取 r 排列,P(n,r) = n!/(n-r)!。
  • **組合** — 無序選擇:從 n 取 r 組合,C(n,r) = n!/(r!(n-r)!)。
  • **全排列** — P(n,n) = n!。

解法一:位元狀態法 (Bitmask) — 適合 n ≤ 20

public class BitmaskPermComb {
    // 全排列:遍歷 0 ~ (1<

優點: 思路直觀、無遞歸堆疊溢位風險。
缺點: 時間複雜度 O(n·2^n),n>20 時極慢;不產生字典序。

解法二:遞歸回溯 — 經典、靈活、產生字典序

全排列

public class BacktrackPerm {
    private static boolean[] used;
    private static int[] path;
    private static int[] nums;

    public static void permute(int[] a) {
        nums = a; used = new boolean[a.length]; path = new int[a.length];
        dfs(0);
    }
    private static void dfs(int depth) {
        if (depth == nums.length) {
            System.out.println(Arrays.toString(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            path[depth] = nums[i];
            dfs(depth + 1);
            used[i] = false; // 回溯
        }
    }
}

組合 C(n,k)

public class BacktrackComb {
    public static void combine(int[] a, int k) {
        combineHelper(a, k, 0, new ArrayList<>());
    }
    private static void combineHelper(int[] a, int k, int start, List path) {
        if (path.size() == k) {
            System.out.println(path);
            return;
        }
        // 剪枝:剩餘元素不足填滿 k
        for (int i = start; i <= a.length - (k - path.size()); i++) {
            path.add(a[i]);
            combineHelper(a, k, i + 1, path);
            path.remove(path.size() - 1);
        }
    }
}

排列組合統一框架 (LeetCode 風格)

public class UnifiedBacktrack {
    // 全排列
    public List> permute(int[] nums) {
        List> res = new ArrayList<>();
        backtrackPerm(nums, new boolean[nums.length], new ArrayList<>(), res);
        return res;
    }
    private void backtrackPerm(int[] nums, boolean[] used, List path, List> res) {
        if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true; path.add(nums[i]);
            backtrackPerm(nums, used, path, res);
            path.remove(path.size()-1); used[i] = false;
        }
    }

    // 組合
    public List> combine(int n, int k) {
        List> res = new ArrayList<>();
        backtrackComb(n, k, 1, new ArrayList<>(), res);
        return res;
    }
    private void backtrackComb(int n, int k, int start, List path, List> res) {
        if (path.size() == k) { res.add(new ArrayList<>(path)); return; }
        for (int i = start; i <= n - (k - path.size()) + 1; i++) {
            path.add(i); backtrackComb(n, k, i+1, path, res); path.remove(path.size()-1);
        }
    }
}

解法三:動態規劃 / 迭代生成 — 空間換時間、適合大量查詢

public class DPComb {
    /** 迭代生成所有組合 C(n,k) — 底層用「下一個組合」算法 */
    public static List> combineIter(int n, int k) {
        List> res = new ArrayList<>();
        int[] comb = new int[k];
        for (int i = 0; i < k; i++) comb[i] = i + 1; // 初始 1,2,..,k
        while (true) {
            res.add(Arrays.stream(comb).boxed().collect(Collectors.toList()));
            // 產生下一個組合
            int i = k - 1;
            while (i >= 0 && comb[i] == n - k + i + 1) i--;
            if (i < 0) break;
            comb[i]++;
            for (int j = i + 1; j < k; j++) comb[j] = comb[j-1] + 1;
        }
        return res;
    }

    /** 迭代生成全排列 — 字典序下一個排列 (std::next_permutation) */
    public static List> permuteIter(int[] a) {
        List> res = new ArrayList<>();
        int[] arr = Arrays.copyOf(a, a.length);
        Arrays.sort(arr); // 必須從最小字典序開始
        do {
            res.add(Arrays.stream(arr).boxed().collect(Collectors.toList()));
        } while (nextPermutation(arr));
        return res;
    }

    /** 字典序下一個排列 */
    private static boolean nextPermutation(int[] a) {
        int i = a.length - 2;
        while (i >= 0 && a[i] >= a[i+1]) i--;
        if (i < 0) return false;
        int j = a.length - 1;
        while (a[j] <= a[i]) j--;
        swap(a, i, j);
        reverse(a, i+1, a.length-1);
        return true;
    }
    private static void swap(int[] a, int i, int j) { int t=a[i]; a[i]=a[j]; a[j]=t; }
    private static void reverse(int[] a, int l, int r) { while(l

效能與選擇指南

演算法時間複雜度空間複雜度輸出順序適用場景
位元狀態O(n·2^n)O(1) 額外二進制序n≤15、教學展示、位運算練習
遞歸回溯O(P(n,k)或C(n,k))O(k) 堆疊字典序通用、面試、需剪枝、需收集結果
迭代 (next_perm/comb)O(輸出大小)O(k)字典序大量資料、記憶體受限、需暫停/繼續

處理重複元素

// 排列含重複:排序後跳過相同未使用元素
Arrays.sort(nums);
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;

// 組合含重複:同理,start 循環中跳過
if (i > start && nums[i] == nums[i-1]) continue;

實務建議

  • **面試/競程**:熟練遞歸回溯模板 + 剪枝技巧。
  • **生產系統**:組合數龐大時**不要**一次性生成所有結果,改用迭代器/生成器模式 (Java Stream / Iterator) 惰性產出。
  • **庫支援**:Apache Commons Math CombinatoricsUtils、Guava Collections2.permutations、自行實作 Spliterator 整合 Stream API。

掌握這三大類演算法,從位元操作的巧思、遞歸回溯的通用框架、到迭代生成的工程化落地,即可應對所有排列組合計算需求。

copyright © 萬盛學電腦網 all rights reserved