Java 全排列實戰：1,2,3,4 組成互不相同的三位數

問題

從 {1,2,3,4} 中選取 3 個不重複數字組成三位數，共有多少個？列出所有。

解法一：三層循環暴力枚舉

public class Permutation3Digit {
    public static void main(String[] args) {
        int count = 0;
        for (int i = 1; i <= 4; i++)       // 百位
            for (int j = 1; j <= 4; j++)   // 十位
                for (int k = 1; k <= 4; k++) { // 個位
                    if (i != j && j != k && i != k) {
                        System.out.println(i*100 + j*10 + k);
                        count++;
                    }
                }
        System.out.println("總共: " + count); // 24
    }
}

解法二：遞歸回溯 (通用全排列模板)

public class PermutationGeneric {
    static int[] nums = {1,2,3,4};
    static boolean[] used = new boolean[5];
    static int[] path = new int[3];
    static int count = 0;

    public static void main(String[] args) {
        dfs(0);
        System.out.println("總共: " + count);
    }

    static void dfs(int depth) {
        if (depth == 3) {
            for (int d : path) System.out.print(d);
            System.out.println();
            count++;
            return;
        }
        for (int i = 0; i < 4; i++) {
            if (!used[i]) {
                used[i] = true;
                path[depth] = nums[i];
                dfs(depth + 1);
                used[i] = false;
            }
        }
    }
}

數學驗證

排列數 P(4,3) = 4 × 3 × 2 = 24，與程序結果一致。

擴展

• 可推廣至任意 n 選 k 排列
• 若允許重複則為 n^k (4^3=64)
• 組合 (不考慮順序) 用 C(n,k)，代碼中 for 起始索引改為 depth