四選三全排列生成：從暴力三層循環到標準排列算法的演進

問題描述

輸入 4 個已排序的不同整數，輸出從中選 3 個數的所有排列（共 24 種）。輸出順序：先固定不選第 4 個數的 6 種排列，再不選第 3 個，依此類推。

原代碼分析

提供的代碼使用 4 組三層循環，每組通過排除某一索引（i!=3, i!=2...）實現「選 3 個」。雖然能產生正確結果，但代碼冗余嚴重，不可擴展。

標準排列算法

使用遞歸回溯或 next_permutation 生成全排列，再取前 3 位。或直接針對 4 選 3 的組合，對每個組合生成 3! = 6 種排列。

改進版代碼

#include <stdio.h>

void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

void permute(int arr[], int l, int r, int k) {
    if (l == r) {
        for (int i = 0; i < k; i++) printf("%d ", arr[i]);
        printf("\n");
        return;
    }
    for (int i = l; i <= r; i++) {
        swap(&arr[l], &arr[i]);
        permute(arr, l+1, r, k);
        swap(&arr[l], &arr[i]);  // 回溯
    }
}

int main() {
    int num[4];
    for (int i = 0; i < 4; i++) scanf("%d", &num[i]);

    // 生成所有 4 選 3 的組合索引
    int indices[4] = {0,1,2,3};
    for (int exclude = 3; exclude >= 0; exclude--) {
        int comb[3], idx = 0;
        for (int i = 0; i < 4; i++) 
            if (i != exclude) comb[idx++] = num[i];
        permute(comb, 0, 2, 3);
    }
    return 0;
}

測試樣例

輸入： 1 2 3 4
輸出： 24 行排列，與樣例完全一致。