如何实现从n个0起始连续数中取m个数的全组合生成函数？

需求描述 #

实现一个C语言函数，输入n（代表从0开始的n个连续数字：0,1,...,n-1）和m，返回从中选取m个数的所有组合构成的二维数组。例如n=5，m=2时，输出应为{{0,1},{0,2},{0,3},{0,4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}。

原代码无法正常运行，代码如下：

int **getSource(int nV, int num){
    int c = num_of_com(nV, num);
    int **source = (int **)malloc(sizeof(int *)*c);
        for(int i=0;i<c;i++){
            source[i] = (int *)malloc(sizeof(int)*num);
            for(int j=nV;j>=num;j--){
                *(*(source+i)+num-1)=j-2;
                if(num>1)
                getSource(nV-1,num-1);
            }
        }
        
    return source;
}

原代码问题分析 #

• 递归逻辑无效：直接在循环中递归调用getSource，但未处理递归返回的结果，也没有将子组合与当前数字拼接，完全没有利用递归的返回值生成有效组合。
• 元素赋值逻辑错误：*(*(source+i)+num-1)=j-2的赋值规则完全不符合组合的生成逻辑，组合要求元素递增且无重复，这行代码无法生成符合要求的元素序列。
• 内存管理混乱：递归调用时重复分配内存，但未将这些内存中的数据合并到最终结果数组，既会造成内存泄漏，也无法收集所有组合。
• 组合数计算依赖缺失：假设num_of_com是计算组合数C(n,m)的函数，若该函数未正确实现，会直接导致内存分配错误。

正确实现方案 #

1. 实现组合数计算函数 #

用于确定结果二维数组的行数，避免内存分配错误：

long long num_of_com(int n, int k) {
    if (k > n) return 0;
    if (k == 0 || k == n) return 1;
    // 取较小值减少计算量，避免溢出
    k = k < n - k ? k : n - k;
    long long res = 1;
    for (int i = 1; i <= k; i++) {
        res = res * (n - k + i) / i;
    }
    return res;
}

2. 实现递归生成组合的辅助函数 #

通过辅助函数跟踪当前组合、起始位置、结果数组和当前结果索引，确保组合按规则生成：

void generate_combinations(int n, int start, int m, int current[], int current_len, int **result, int *index) {
    // 当前组合长度达到m时，复制到结果数组
    if (current_len == m) {
        for (int i = 0; i < m; i++) {
            result[*index][i] = current[i];
        }
        (*index)++;
        return;
    }
    // 剪枝：剩余数字不足以凑够m个时，停止遍历
    for (int i = start; i <= n - (m - current_len); i++) {
        current[current_len] = i;
        // 递归生成下一个元素，起始位置+1避免重复组合
        generate_combinations(n, i + 1, m, current, current_len + 1, result, index);
    }
}

3. 主函数实现 #

负责内存分配、调用辅助函数生成组合，并返回结果：

int **getSource(int nV, int num) {
    // 边界情况处理：无合法组合时返回NULL
    if (num > nV || num == 0) return NULL;
    
    long long combo_count = num_of_com(nV, num);
    // 分配二维数组内存
    int **source = (int **)malloc(sizeof(int *) * combo_count);
    for (int i = 0; i < combo_count; i++) {
        source[i] = (int *)malloc(sizeof(int) * num);
    }
    
    // 临时数组存储当前正在生成的组合
    int *current = (int *)malloc(sizeof(int) * num);
    int index = 0;
    generate_combinations(nV, 0, num, current, 0, source, &index);
    
    free(current); // 释放临时数组
    return source;
}

使用注意事项 #

• 内存释放：调用getSource获取结果后，需要手动释放内存，避免泄漏：

int **res = getSource(5, 2);
long long count = num_of_com(5, 2);
for (int i = 0; i < count; i++) {
    free(res[i]);
}
free(res);

• 溢出处理：组合数计算使用long long类型，避免nV较大时int类型溢出。

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