Java 練習題：從 1、2、3、4 組成互不相同的三位數（全排列應用）

題目

有數字 1、2、3、4，能組成多少個互不相同且無重複數字的三位數？請列出所有數字並統計個數。

數學分析

這是經典的排列問題：從 4 個不同元素中取 3 個，順序敏感，不重複。
排列數 P(4,3) = 4 × 3 × 2 = 24 個。

解法一：三層循環 + 條件過濾（直觀易懂）

public class ThreeDigitPermutation {
    public static void main(String[] args) {
        int count = 0;
        System.out.println("符合條件的三位數：");
        
        for (int i = 1; i <= 4; i++) {       // 百位
            for (int j = 1; j <= 4; j++) {   // 十位
                for (int k = 1; k <= 4; k++) { // 個位
                    // 核心判斷：三位數字兩兩不相等
                    if (i != j && i != k && j != k) {
                        int num = i * 100 + j * 10 + k;
                        System.out.print(num + " ");
                        count++;
                        if (count % 6 == 0) System.out.println(); // 每行 6 個
                    }
                }
            }
        }
        System.out.println("\n總共 " + count + " 個。");
    }
}

解法二：字符串拼接分割法（原始代碼風格，不推薦生產）

public class StringSplitMethod {
    public static void main(String[] args) {
        String str = "";
        // 1. 生成所有 4³=64 種組合（含重複）
        for (int i = 1; i <= 4; i++)
            for (int j = 1; j <= 4; j++)
                for (int k = 1; k <= 4; k++)
                    str = (i*100 + j*10 + k) + "#" + str; // 頭插法
        
        // 2. 分割並過濾
        String[] arr = str.split("#");
        int count = 0;
        for (String s : arr) {
            if (s.length() != 3) continue; // 過濾空串
            char a = s.charAt(0), b = s.charAt(1), c = s.charAt(2);
            if (a != b && b != c && a != c) {
                System.out.print(s + " ");
                count++;
            }
        }
        System.out.println("\n總共 " + count + " 個。");
    }
}

解法三：遞歸回溯（通用全排列模板，可擴展）

import java.util.*;

public class PermutationBacktrack {
    private static List result = new ArrayList<>();
    
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        boolean[] used = new boolean[5]; // 索引 1-4
        backtrack(nums, used, new StringBuilder(), 3);
        
        System.out.println("結果: " + result);
        System.out.println("總數: " + result.size());
    }
    
    private static void backtrack(int[] nums, boolean[] used, StringBuilder path, int targetLen) {
        if (path.length() == targetLen) {
            result.add(Integer.parseInt(path.toString()));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[nums[i]]) continue;
            used[nums[i]] = true;
            path.append(nums[i]);
            backtrack(nums, used, path, targetLen);
            path.deleteCharAt(path.length() - 1);
            used[nums[i]] = false;
        }
    }
}

解法四：Java 8 Stream API（函數式風格）

import java.util.stream.*;

public class StreamPermutation {
    public static void main(String[] args) {
        IntStream.rangeClosed(1, 4) // 百位 1-4
            .boxed()
            .flatMap(i -> IntStream.rangeClosed(1, 4) // 十位 1-4
                .filter(j -> j != i)
                .boxed()
                .flatMap(j -> IntStream.rangeClosed(1, 4) // 個位 1-4
                    .filter(k -> k != i && k != j)
                    .mapToObj(k -> i * 100 + j * 10 + k)
                )
            )
            .peek(System.out::println)
            .count(); // 終端操作觸發執行
    }
}

運行結果（24 個數字）

123 124 132 134 142 143
213 214 231 234 241 243
312 314 321 324 341 342
412 413 421 423 431 432
總共 24 個。

算法複雜度對比

面試擴展題

1. 如果允許重複數字：4³ = 64 個（去掉 i!=j... 判斷）
2. 如果數字包含 0 且百位不能為 0：百位 1-9，十位個位 0-9，排除重複
3. 泛化為從 n 個數字中取 k 位組成數字：回溯模板直接復用
4. 求所有排列之和：數學公式計算，避免枚舉（大數時必須）

最佳實踐：固定小規模（如 4 選 3）用三層循環+條件判斷最直觀高效；可變規模/需通用模板用回溯法；面試手寫代碼首選回溯模板展示算法功力。