找到一个函数/算法来保存c语言中数组的数组(矩阵)中的每个数组(包含0和1)的组合

Question

我正试图找到一种方法来保存一个int数组在c数组的int数组的每一个组合，所以我有一个矩阵的结果。该数组只包含1和0。

数组的长度是k，数组中1的个数是l，所以结果(矩阵)的长度是l!/(k!*(l-k)!)

下面是一个例子:

unsigned int l = 2;
unsigned int k = 4;

第一个数组是:

short first_array = {1, 1, 0, 0};

结果应该是:

short result[][] = {
{1, 1, 0, 0},
{1, 0, 1, 0},
{1, 0, 0, 1},
{0, 1, 1, 0},
{0, 1, 0, 1},
{0, 0, 1, 1}
};

结果可以是short类型，因为它比int类型使用更少的内存，并且只需要保存值0和1。我要用6 &lt做几十万次;l & lt;14、所以内存效率会很高。

我尝试做一个二进制枚举，但这是非常低效的，因为我必须检查我的子结果是否包含l个1，然后将它添加到我的结果数组。

我读过关于递归函数可以做这样的任务，但我不明白如何。我无法想象我的代码最终应该是什么样子，以及我的问题如何解决。

Answer 1

您可以使用递归函数来完成此操作，该函数尝试在从i = 0到k的每个单元格中放入0和1，然后递归到剩余的数组中进行填充。如果调用达到了所有l值都被使用的点，则发出一个结果。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void permute(
short **result,
short *a,
unsigned int l,
unsigned int k,
unsigned int i,
unsigned int *result_len
) {
if (l <= 0) {
result[*result_len] = malloc(sizeof(*a) * k);
memcpy(result[*result_len], a, sizeof(*a) * k);
(*result_len)++;
}
else if (i < k) {
a[i] = 1;
permute(result, a, l - 1, k, i + 1, result_len);
a[i] = 0;
permute(result, a, l, k, i + 1, result_len);
}
}
int main() {
unsigned int l = 2;
unsigned int k = 4;
short a[k];
short *result[6];
unsigned int result_len = 0;
memset(a, 0, k * sizeof(*a));
permute(result, a, l, k, 0, &result_len);
for (int i = 0; i < result_len; i++) {
for (int j = 0; j < k; j++) {
printf("%d ", result[i][j]);
}
puts("");
free(result[i]);
}
return 0;
}

输出:

1 1 0 0 
1 0 1 0 
1 0 0 1 
0 1 1 0 
0 1 0 1 
0 0 1 1 

调用者可以预先分配所有的结果数组，动态计算正确的结果数组长度，并且可以有一个帮助函数对客户机隐藏一些参数，但是我将这些作为练习留给读者。

还有其他优化，比如如果我们看到我们接近数组的末尾，并且没有足够的空间来填充l1s，就会提前退出。