如何在C中创建int数组的所有可能组合(而不是排列)

Question

我想生成int的所有可能组合，例如：对于集合[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;
}