C语言中实现动态层数嵌套循环的数组可重复组合遍历

假设有一个包含N个元素的数组（示例中N=4）：

#define ELEMENT_COUNT 4
char arr[ELEMENT_COUNT] = { 'a', 'b', 'c', 'd' };

如果要生成长度固定的可重复元素对，两层嵌套循环就能轻松实现：

for (int i = 0; i < ELEMENT_COUNT; i++)
    for (int j = 0; j < ELEMENT_COUNT; j++)
        printf("%c %c\n", arr[i], arr[j]);

但如果需要生成长度为3、4，甚至运行时才能确定长度的所有可重复元素组合，手动编写多层嵌套循环显然不现实。下面提供两种可行的实现方案：

方案一：递归实现 #

递归的核心思路是：每次为当前位置选择一个元素，递归处理剩余位置，当组合长度达到目标值时输出结果。

代码示例 #

#include <stdio.h>
#include <stdlib.h>

#define ELEMENT_COUNT 4
char arr[ELEMENT_COUNT] = { 'a', 'b', 'c', 'd' };

// 递归生成组合：result存储当前组合，current_pos为当前填充位置，target_length为目标长度
void generate_combinations(char *result, int current_pos, int target_length) {
    if (current_pos == target_length) {
        // 输出当前组合
        for (int i = 0; i < target_length; i++) {
            printf("%c ", result[i]);
        }
        printf("\n");
        return;
    }

    // 遍历所有元素，为当前位置赋值后递归
    for (int i = 0; i < ELEMENT_COUNT; i++) {
        result[current_pos] = arr[i];
        generate_combinations(result, current_pos + 1, target_length);
    }
}

int main() {
    int target_length;
    printf("请输入组合长度：");
    scanf("%d", &target_length);

    // 分配存储当前组合的内存
    char *result = (char*)malloc(target_length * sizeof(char));
    if (result == NULL) {
        perror("内存分配失败");
        return 1;
    }

    generate_combinations(result, 0, target_length);

    free(result);
    return 0;
}

逻辑说明 #

• 递归函数每次负责填充组合的一个位置，当current_pos等于target_length时，说明组合已生成完成，直接输出。
• 外层循环遍历数组所有元素，为当前位置赋值后，递归调用自身处理下一个位置，直到所有位置填充完毕。

方案二：迭代实现 #

如果不想使用递归，可以采用迭代方式：将每个组合看作ELEMENT_COUNT进制的数，用索引数组记录每个位置的元素下标，通过“进位”逻辑遍历所有可能的组合。

代码示例 #

#include <stdio.h>
#include <stdlib.h>

#define ELEMENT_COUNT 4
char arr[ELEMENT_COUNT] = { 'a', 'b', 'c', 'd' };

int main() {
    int target_length;
    printf("请输入组合长度：");
    scanf("%d", &target_length);

    // 初始化索引数组，所有位置初始为0
    int *indices = (int*)calloc(target_length, sizeof(int));
    if (indices == NULL) {
        perror("内存分配失败");
        return 1;
    }

    while (1) {
        // 输出当前组合
        for (int i = 0; i < target_length; i++) {
            printf("%c ", arr[indices[i]]);
        }
        printf("\n");

        // 进位逻辑：从最后一位开始递增，溢出则置0并向前进位
        int pos = target_length - 1;
        while (pos >= 0) {
            indices[pos]++;
            if (indices[pos] < ELEMENT_COUNT) {
                break;
            }
            indices[pos] = 0;
            pos--;
        }

        // 所有位都溢出，说明所有组合已生成，退出循环
        if (pos < 0) {
            break;
        }
    }

    free(indices);
    return 0;
}

逻辑说明 #

• 用indices数组记录每个位置选择的元素下标，初始全为0。
• 每次先输出当前索引对应的组合，然后从最后一位开始递增索引：如果当前索引未超出数组范围，停止进位；否则将当前位置索引置0，向前一位继续进位。
• 当所有位都溢出（pos < 0）时，说明所有可能的组合已遍历完成，终止循环。

内容的提问来源于stack exchange，提问作者trxgnyp1