有重复元素的全排列问题 c语言

在C语言中，处理有重复元素的全排列问题可以采用递归或者回溯法。由于存在重复元素，普通的排列算法如递推公式（阶乘除以每个数的阶乘）将不再适用，因为这会导致某些排列被计算多次。

一种常见的解决方案是使用哈希集合（例如数组或动态数据结构）来跟踪已经访问过的元素，避免重复生成相同的排列。以下是使用递归的简单示例：

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

bool used[100]; // 假设我们有最多100个元素

void permute(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 (!used[i]) {  // 如果元素未使用
                used[i] = true;  // 标记为已使用
                arr[start] = i;  // 将当前元素放入起始位置
                permute(start + 1, end);  // 递归调用，处理剩余的位置
                used[i] = false;  // 撤销操作，尝试下一个未使用的元素
            }
        }
    }
}

int main() {
    int arr[] = {1, 2, 2, 3};  // 有重复元素的数组
    int n = sizeof(arr) / sizeof(arr[0]);

    permute(0, n - 1);

    return 0;
}