在C语言中生成含指定1的个数的0-1数组所有组合的高效算法

要实现生成所有长度为k、恰好包含l个1的0-1数组，并存储为二维short数组，核心是用递归剪枝的方法直接生成符合要求的组合，避免无效枚举，同时优化内存使用。

核心思路 #

递归的核心逻辑是逐个确定数组的每个位置值，同时跟踪剩余需要放置的1的数量：

• 若剩余需要放置的1的数量等于剩余未处理的位置数，剩余位置全部填1，结束当前分支
• 若剩余需要放置的1的数量为0，剩余位置全部填0，结束当前分支
• 否则分两种情况递归：当前位置填1（剩余1的数量减1）、当前位置填0（剩余1的数量不变），同时提前剪枝——当剩余位置数不足以放下剩余的1时，跳过填0的分支

内存优化要点 #

• 使用short类型存储每个元素：0和1仅需16位即可表示，相比int节省50%内存
• 采用连续内存分配：先分配一块足够存储所有元素的连续内存，再用指针数组映射每行起始地址，避免内存碎片化，提升缓存命中率

完整代码实现 #

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

// 计算组合数C(k,l)，优化计算避免溢出
unsigned long long comb(unsigned int k, unsigned int l) {
    if (l > k - l) l = k - l; // 取较小的项减少计算量
    unsigned long long res = 1;
    for (unsigned int i = 1; i <= l; i++) {
        res = res * (k - l + i) / i;
    }
    return res;
}

// 递归生成所有符合要求的组合
void generate_combinations(int pos, int remaining_ones, short *current_row, short **result, int *row_idx, int k) {
    if (pos == k) {
        // 复制当前行到结果矩阵
        for (int i = 0; i < k; i++) {
            result[*row_idx][i] = current_row[i];
        }
        (*row_idx)++;
        return;
    }

    // 当前位置填1（剩余1的数量>0时才可行）
    if (remaining_ones > 0) {
        current_row[pos] = 1;
        generate_combinations(pos + 1, remaining_ones - 1, current_row, result, row_idx, k);
    }

    // 当前位置填0（剩余位置需能放下剩余的1）
    if ((k - pos - 1) >= remaining_ones) {
        current_row[pos] = 0;
        generate_combinations(pos + 1, remaining_ones, current_row, result, row_idx, k);
    }
}

int main() {
    unsigned int l = 2;
    unsigned int k = 4;

    unsigned long long total_rows = comb(k, l);
    if (total_rows == 0) {
        printf("参数错误：k必须大于等于l\n");
        return 1;
    }

    // 分配连续内存存储所有元素
    short *data = (short *)malloc(total_rows * k * sizeof(short));
    // 分配指针数组映射每行
    short **result = (short **)malloc(total_rows * sizeof(short *));
    for (unsigned long long i = 0; i < total_rows; i++) {
        result[i] = data + i * k;
    }

    short *current_row = (short *)malloc(k * sizeof(short));
    int row_idx = 0;

    generate_combinations(0, l, current_row, result, &row_idx, k);

    // 打印结果示例
    printf("short result[][] = {\n");
    for (unsigned long long i = 0; i < total_rows; i++) {
        printf("    {");
        for (int j = 0; j < k; j++) {
            printf("%d", result[i][j]);
            if (j != k - 1) printf(", ");
        }
        printf("}");
        if (i != total_rows - 1) printf(",");
        printf("\n");
    }
    printf("};\n");

    // 释放内存
    free(current_row);
    free(result);
    free(data);

    return 0;
}

效率说明 #

递归剪枝的方式直接生成符合要求的组合，无需枚举所有可能再校验1的数量。以k=20、l=10为例，二进制枚举需遍历1048576次，而递归仅生成184756次有效组合，效率提升显著，完全适配数十万次执行的场景。

内容的提问来源于stack exchange，提问作者201st Luka