C语言算法实现数组的全排列（含重复元素）

设 R = {r1，r2，……，rn} 是要进行排列的n个元素。其中元素 r1，r2，……，rn 可能相同。设计一个C语言算法，列出R的所有不同排列。

例如，假设元素为：

int x[] = {1, 2, 2, 3, 3};

求其全排列。

算法实现

以下是一个递归算法的示例，用于列出给定数组的所有不同排列：

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

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

bool isDuplicate(int arr[], int start, int end) {
    for (int i = start; i < end; i++) {
        if (arr[i] == arr[end]) {
            return true;
        }
    }
    return false;
}

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++) {
            if (!isDuplicate(arr, start, i)) {
                swap(&arr[start], &arr[i]);
                permute(arr, start + 1, end);
                swap(&arr[start], &arr[i]);
            }
        }
    }
}

int main() {
    int x[] = {1, 2, 2, 3, 3};
    int n = sizeof(x) / sizeof(x[0]);
    permute(x, 0, n - 1);
    return 0;
}

算法解释

1. isDuplicate 函数: 该函数用于判断数组中从 start 到 end 的元素是否与 arr[end] 相同。如果相同，则返回 true，否则返回 false。
2. permute 函数: 该函数使用递归的方式生成所有排列。
   • 当 start == end 时，表示已经到达数组的最后一个元素，输出当前排列。
   • 否则，从 start 到 end 遍历数组，对于每个元素 arr[i]，如果它不是重复元素，则将它与 arr[start] 交换，然后递归调用 permute 函数处理剩下的元素。最后，将 arr[start] 和 arr[i] 再交换回来，还原数组。

输出结果

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

总结

该算法可以有效地列出给定数组（包含重复元素）的所有不同排列。通过判断元素是否重复，可以避免生成重复排列。