如何在 C 中创建整数数组的所有可能组合（而不是排列）？

Question

我想生成所有可能的整数组合，例如： 对于集合 [1, 2, 3]；所有组合都是：

[
  [],       [ 3 ],
  [ 2 ],    [ 3, 2 ],
  [ 1 ],    [ 3, 1 ],
  [ 2, 1 ], [ 3, 2, 1 ]
]

我知道如何在 javascript 中做到这一点，但无法找出如何在 C 中做到这一点。 javascript 版本：

const combinations = (elements) => {
    if (elements.length === 0) return [[]];
    const firstEl = elements[0];
    const rest = elements.slice(1);

    const combsWithoutFirst = combinations(rest);
    const combsWithFirst = [];

    combsWithoutFirst.forEach(combs => {
        const combWithFirst = [...combs, firstEl];
        combsWithFirst.push(combWithFirst);
    });

    return [...combsWithoutFirst, ...combsWithFirst];
}

console.log(combinations([1, 2, 3]));

那么 c 版本可能是什么？

编辑：我到目前为止的版本，但无法正常工作：

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

typedef struct
{
    int *values;
    size_t size;
} comb;

comb *combinations;
size_t depth;
int count;

void init()
{
    count = 1; // number of combintations so far
    int size = depth;
    for (int i = 0; i < depth; i++)
    {
        size *= 2;
    }
    combinations = malloc(sizeof(comb) * size);
}

comb *ctor(int *values, size_t size)
{
    comb *newone = malloc(sizeof(comb));
    newone->values = values;
    newone->size = size;
    return newone;
}

comb *pop_front(comb x)
{
    int newSize = x.size - 1;
    int *newVals = malloc(sizeof(int) * newSize);
    memcpy(newVals, x.values + sizeof(int), newSize);
    return ctor(newVals, newSize);
}

comb *push_back(comb x, int newValue)
{
    int newSize = x.size + 1;
    int *newVals = malloc(sizeof(int) * newSize);
    memcpy(newVals, x.values, x.size * sizeof(int));
    newVals[newSize - 1] = newValue;
    return ctor(newVals, newSize);
}

void addComb(comb *x, comb y)
{
}

comb *func(comb *elements)
{
    if (!depth)
    {
        return ctor(NULL, 0);
    }
    int firstEl = elements->values[0];
    comb *rest = pop_front(*elements);

    depth--;
    comb *combsWithoutFirst = func(rest);
    comb *combsWithFirst = ctor(NULL, 0);

    for (int i = 0; i < count; i++)
    {
        comb *combWithFirst = push_back(combsWithoutFirst[i], firstEl);
        // now add that combWithFirst to the combsWithFirst
    }

    // merge the two arrays
}

int main()
{
}

Answer 1

一种简单的方法是使用位集。我想 64 位已经足够了。

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

void comb(int *set, size_t n) {
    assert(n < 64);
    
    uint64_t bits = 0;
    uint64_t end = 1 << n;
    while (bits < end) {
        printf("[");
        for (size_t i = 0; i < n; ++i) {
            if (bits & (1 << i)) {
                printf("%d ", set[i]);
            }
        }
        printf("]\n");

        bits++;
    }
}

int main(void) {
    int set[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    comb(set, 10);

    return 0;
}