Java 全排列的幾種實現(xiàn)方法

更新時間：2024年11月26日 11:14:50 作者：飛滕人生TYF

本文詳細介紹了Java中全排列問題的幾種實現(xiàn)方法,包括回溯法、字典序排列法和迭代法,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧

1. 全排列問題定義

輸入： 給定一個序列或數(shù)組，找出所有元素的排列。
輸出： 返回所有可能的排列。

示例：

輸入：[1, 2, 3]

輸出：

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

2. 常用算法

全排列的常見實現(xiàn)方法：

回溯法（Backtracking）
字典序排列法（Lexicographic Order）
迭代法（非遞歸實現(xiàn)）

3. 使用回溯法解決全排列

回溯法是一種基于遞歸的搜索算法，它通過不斷嘗試并撤銷之前的選擇來生成所有可能的解。

3.1 回溯法實現(xiàn)（基礎版）

適用于數(shù)組中無重復元素的全排列。

import java.util.ArrayList;
import java.util.List;

public class Permutations {
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        boolean[] used = new boolean[nums.length]; // 標記是否使用過
        List<Integer> current = new ArrayList<>();
        backtrack(nums, used, current, result);
        return result;
    }

    private static void backtrack(int[] nums, boolean[] used, List<Integer> current, List<List<Integer>> result) {
        // 終止條件：當前排列的大小等于數(shù)組長度
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current)); // 將當前排列加入結果
            return;
        }
        // 遍歷每個元素
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) { // 跳過已使用的元素
                continue;
            }
            // 做選擇
            current.add(nums[i]);
            used[i] = true;
            // 遞歸
            backtrack(nums, used, current, result);
            // 撤銷選擇
            current.remove(current.size() - 1);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> permutations = permute(nums);
        System.out.println(permutations);
    }
}

輸出結果

對于輸入 [1, 2, 3]：

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

3.2 回溯法（不使用標記數(shù)組）

通過交換數(shù)組中的元素，可以避免使用標記數(shù)組。

import java.util.ArrayList;
import java.util.List;

public class PermutationsSwap {
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, result);
        return result;
    }

    private static void backtrack(int[] nums, int start, List<List<Integer>> result) {
        if (start == nums.length) {
            List<Integer> permutation = new ArrayList<>();
            for (int num : nums) {
                permutation.add(num);
            }
            result.add(permutation);
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i); // 交換元素
            backtrack(nums, start + 1, result);
            swap(nums, start, i); // 撤銷交換
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> permutations = permute(nums);
        System.out.println(permutations);
    }
}

3.3 回溯法處理重復元素

如果數(shù)組中包含重復元素（例如 [1, 1, 2]），我們需要對結果去重?？梢酝ㄟ^對數(shù)組排序并在遞歸時跳過重復元素來實現(xiàn)。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PermutationsWithDuplicates {
    public static List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums); // 排序以便跳過重復元素
        boolean[] used = new boolean[nums.length];
        backtrack(nums, used, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int[] nums, boolean[] used, List<Integer> current, List<List<Integer>> result) {
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            // 跳過相鄰重復的元素
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            current.add(nums[i]);
            used[i] = true;
            backtrack(nums, used, current, result);
            current.remove(current.size() - 1);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 2};
        List<List<Integer>> permutations = permuteUnique(nums);
        System.out.println(permutations);
    }
}

輸出結果

對于輸入[1, 1, 2]：

[[1, 1, 2], [1, 2, 1], [2, 1, 1]]

4. 字典序排列法

字典序法生成全排列的步驟：

找到當前排列的“最后一個升序對”。
從右側找到比升序對中較小值大的最小值，交換這兩個值。
將右側部分反轉。

適用于需要按字典序輸出排列的情況。

import java.util.Arrays;

public class PermutationsLexicographic {
    public static void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) { // 找到升序對
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j); // 交換
        }
        reverse(nums, i + 1); // 反轉后面的部分
    }

    private static void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println(Arrays.toString(nums));
        for (int i = 0; i < 6; i++) {
            nextPermutation(nums);
            System.out.println(Arrays.toString(nums));
        }
    }
}

5. 總結

常見方法對比

方法	適用場景	特點
回溯法	全排列（通用）	最常用，適合生成所有排列，可以處理重復元素，通過遞歸和剪枝實現(xiàn)。
交換法	無重復全排列	不需要額外空間標記數(shù)組，通過交換實現(xiàn)排列，但對重復元素需要額外處理。
字典序排列法	字典序輸出排列	按字典序生成排列，適合序列化輸出；需要對輸入序列進行排序作為初始狀態(tài)。
迭代法	生成排列的特定場景	使用循環(huán)代替遞歸，但實現(xiàn)起來較為復雜，適合排列生成問題中的迭代優(yōu)化。