C语言递归算法生成n个元素全排列 - 思路与代码实现

生成n个元素的全排列可以使用递归算法来实现，思路如下：

1. 如果只有一个元素，则直接返回该元素的排列即可。
2. 否则，选择当前元素ri作为排列的第一个元素，递归生成其余n-1个元素的全排列。
3. 将第一个元素ri与其余n-1个元素的全排列进行组合，得到n个元素的全排列。
4. 重复上述步骤，将所有元素都作为第一个元素，递归生成其余n-1个元素的全排列，并将结果进行合并。

具体的递归算法代码如下所示：

#include <stdio.h>

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

void permute(int arr[], int start, int end) {
    if (start == end) {
        for (int i = 0; i <= end; i++) {
            printf('%d ', arr[i]);
        }
        printf('\n');
    } else {
        for (int i = start; i <= end; i++) {
            swap(&arr[start], &arr[i]);
            permute(arr, start + 1, end);
            swap(&arr[start], &arr[i]); // 恢复数组的原始顺序
        }
    }
}

int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    permute(arr, 0, n - 1);
    return 0;
}

上述代码中的permute函数是递归生成全排列的核心部分。在每次递归调用中，通过交换数组元素的位置，将当前元素作为排列的第一个元素，并递归生成其余元素的全排列。在递归结束后，需要将数组的元素恢复到原始的顺序。

运行上述代码，输出为：

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 2 1 
3 1 2 

可以看到，输出了3个元素{1, 2, 3}的全排列。