核心思想

假設陣列含 n 個元素，依序取出每個元素作為頭元素，然後對剩餘元素進行全排列。例如 1,2,3 的全排列即分別以 1、2、3 開頭的全排列。以 1 開頭的全排列即 2,3 的全排列，以此類推。

設全排列 R(n1,n2,...,nn)，可化簡為分別以 n1,n2,...,nn 開頭的全排列：

n1 R1(n2,n3,...,nn)
n2 R2(n1,n3,...,nn)
...
nn Rn(n1,n2,...,n(n-1))

其中 R1 又可按 R 方式繼續分解，遞歸得到完整全排列。

遞歸函數設計

• index：遞歸過程中子序列在原始序列中的起始位置。
• num：當前子序列長度。
• LENGTH：原始陣列長度（固定不變）。

完整代碼

#include <iostream>
using namespace std;

void permutation(int values[], int index, int num, int LENGTH) {
    int i = 0;
    if (num == 0) { // 找到一個全排列，輸出
        for (i = 0; i < LENGTH; ++i)
            cout << values[i] << " ";
        cout << endl;
        return;
    }
    for (i = 0; i < num; i++) {
        swap(values[index + i], values[index]); // 交換，保證子序列首元素與每個元素交換一次
        permutation(values, index + 1, num - 1); // 對剩餘元素全排列
        swap(values[index], values[index + i]); // 還原陣列，避免重複結果
    }
    return;
}

int main() {
    int values[] = {1, 3, 5};
    permutation(values, 0, 3, 3);
    cout << endl << endl;
    for (int i = 0; i < 3; ++i)
        cout << values[i] << ' ';
    cout << endl << endl;
    return 0;
}