I am trying to find a way to save every combinations of an int array in an int array of arrays in C. So I have a matrix as a result. The array contains only ones and zeros.

The length of the array is k and the number of ones in my array is l. So the length of the result (matrix) is l!/(k!*(l-k)!).

Here is an example:

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

So the first array is:

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

And the result should be:

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}
};

The result can be of type short because it uses less memory than an int and only the values 0 and 1 have to be saved. I have to do this several hundred thousand times with 6 < l < 14, so memory efficiency would be great.

I tried to do a binary enumerating, but this is very inefficient because I have to check if my sub result contains l ones and then add it to my result array.

I read about recursive functions that can do such tasks but I do not understand how. I can not imagine how my code should look like in the end and how my problem can be solved.

CodePudding user response：

You can do this with a recursive function that tries putting a 0 and a 1 in each cell from i = 0 to k, then recurses on the remaining array left to fill. If a call reaches a point where all l values have been used, emit a result.

#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;
}

Output:

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

The caller could pre-allocate all of the result arrays, dynamically compute the correct result array length, and there could be a helper function to hide some of the parameters from the client, but I left these as exercises for the reader.

There are other optimizations, like bailing out early if we see that we're nearing the end of the array and there won't be enough spaces left to fill with l 1s.