C語言實作排列組合：1,2,3,4 組成不重複三位數完整解析

編輯：關於C語言

C語言實作排列組合：1,2,3,4 組成不重複三位數完整解析

經典入門題目：從數字集合 {1,2,3,4} 中取出三個互不相同的數字，組成三位數。共有多少種組合？列出所有組合。本文提供三層巢狀迴圈暴力解法、遞迴回溯通用解法、以及數學排列公式驗譐，並分析時間空間複雜度與擴展應用。

暴力解法：三層迴圈 + 去重判斷

#include <stdio.h>
#include <stdlib.h>

int main() {
    int i, j, k;
    int count = 0;
    int number;

    for (i = 1; i <= 4; i++) {
        for (j = 1; j <= 4; j++) {
            for (k = 1; k <= 4; k++) {
                if (i != j && i != k && j != k) {  // 確保三數互不相同
                    count++;
                    number = 100 * i + 10 * j + k;
                    printf("%5d", number);
                }
            }
        }
    }
    printf("\nTotal count = %d\n", count);
    system("pause");
    return 0;
}

執行結果

  123  124  132  134  142  143
  213  214  231  234  241  243
  312  314  321  324  341  342
  412  413  421  423  431  432
Total count = 24

數學驗證：排列數公式

從 4 個不同元素中取 3 個排序，屬於排列問題：

P(4,3) = 4! / (4-3)! = 4 × 3 × 2 = 24

與程式輸出完全一致。

通用解法：遞迴回溯生成排列

適用於任意 n 個元素取 m 個排列，擴展性極強。

#include <stdio.h>
#include <stdbool.h>

#define MAX_N 10

int n = 4;      // 元素個數
int m = 3;      // 取出個數
int arr[MAX_N] = {1, 2, 3, 4};  // 元素池
int perm[MAX_N];                 // 當前排列
bool used[MAX_N];                // 使用標記
int count = 0;

void backtrack(int depth) {
    if (depth == m) {
        // 輸出當前排列
        for (int i = 0; i < m; i++) {
            printf("%d", perm[i]);
        }
        printf(" ");
        count++;
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            used[i] = true;
            perm[depth] = arr[i];
            backtrack(depth + 1);
            used[i] = false;  // 回溯
        }
    }
}

int main() {
    backtrack(0);
    printf("\nTotal: %d\n", count);
    return 0;
}

複雜度分析與優化方向

解法	時間複雜度	空間複雜度	適用場景
三層迴圈	O(n³)	O(1)	固定小規模、簡單直觀
遞迴回溯	O(P(n,m))	O(m) 遞迴棧 + O(n) 標記	通用排列生成、n、m 可變
下一個排列算法	O(P(n,m) × m)	O(1)	字典序生成、無遞迴開銷

進階擴展應用

組合生成：去除順序要求，只保留遞增序列 i < j < k，即為 C(4,3)=4 種組合。
含重複元素排列：對元素排序，跳過相同元素的重複選擇 if (i>0 && arr[i]==arr[i-1] && !used[i-1]) continue;。
全排列：m = n，生成 n! 種排列。
八皇后、數獨、圖著色：回溯法核心框架通用於約束滿足問題。