Generating the powerset in C

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP





.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;







up vote
9
down vote

favorite
1












I am solving another problem in leetcode.




Given a set, generate all the subsets of the set.



Input: [1,2,3]

Output: [ [3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],]




The solution is accepted but I would like to improve on my C coding style. I have created a node_t type to encapsulate the data related each subset. There could be less verbose ways to do this. Two popular methods of solving this problem seem to be:



  1. backtracking

  2. a subset equals to binary number ≤ n where n is element count.

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


typedef struct node_s 
 int *array;
 int size;
 struct node_s *next;
 node_t;

node_t* alloc_node()

 return (node_t*)malloc(sizeof(node_t));


void free_node(node_t *node)

 free(node);

#define SIZE 3

void print_one(int *one)

 printf("%d ", *one);

void print_1d_array(int *array, int size)

 for(int i = 0; i < size; i++) 
 print_one(&array[i]);
 
 printf("n");

void print_2d_array(int **array, int *col_sizes, int size)

 for (int i = 0; i < size; i++) 
 print_1d_array(array[i], col_sizes[i]);
 

int** create_solution_array(node_t *head, int ans_size, int **column_sizes)

 int **ans = (int**)malloc(sizeof(int*)*ans_size);

 node_t *iter;
 iter = head->next;
 int idx = 0;
 while(iter) 
 ans[idx] = iter->array;
 (*column_sizes)[idx] = iter->size;
 idx++;
 iter = iter->next;
 
 return ans;


void gen_powerset(int *num, int num_size, int idx, int cur_size, int *cur, node_t **iter_node, int *ans_size) 
 if (idx == num_size) 
 node_t *new_node = alloc_node();
 if (cur_size) 
 new_node->array = (int *) malloc(sizeof(int) * cur_size);
 new_node->size = cur_size ;
 memcpy(new_node->array, cur, cur_size*sizeof(int));
 
 (*iter_node)->next = new_node;
 *iter_node = new_node;
 (*ans_size)++;
 return;
 

 gen_powerset(num, num_size, idx + 1, cur_size, cur, iter_node, ans_size);
 *(cur + cur_size) = num[idx];
 gen_powerset(num, num_size, idx + 1, cur_size + 1, cur, iter_node, ans_size);


int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize) 
 node_t *head = alloc_node();
 node_t *iter = head;
 int *cur = (int*)malloc(sizeof(int)*numsSize);
 gen_powerset(nums, numsSize, 0, 0, cur, &iter, returnSize);
 return create_solution_array(head, *returnSize, columnSizes);



int main ()

 int *nums = (int*)malloc(sizeof(int)*SIZE);
 for (int i = 0; i < SIZE; i++) 
 nums[i] = i+1;
 
 int *col_sizes = (int*)malloc(sizeof(int)*SIZE);
 int ans_size;
 int ** ans = subsets(nums, SIZE, &col_sizes, &ans_size);
 print_2d_array(ans, col_sizes, ans_size);
 return 0;




c programming-challenge combinatorics depth-first-search




share|improve this question






















  • @Toby Speight Added problem description.
    – wispymisty
    Sep 7 at 13:25
















up vote
9
down vote

favorite
1












I am solving another problem in leetcode.




Given a set, generate all the subsets of the set.



Input: [1,2,3]

Output: [ [3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],]




The solution is accepted but I would like to improve on my C coding style. I have created a node_t type to encapsulate the data related each subset. There could be less verbose ways to do this. Two popular methods of solving this problem seem to be:



  1. backtracking

  2. a subset equals to binary number ≤ n where n is element count.

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


typedef struct node_s 
 int *array;
 int size;
 struct node_s *next;
 node_t;

node_t* alloc_node()

 return (node_t*)malloc(sizeof(node_t));


void free_node(node_t *node)

 free(node);

#define SIZE 3

void print_one(int *one)

 printf("%d ", *one);

void print_1d_array(int *array, int size)

 for(int i = 0; i < size; i++) 
 print_one(&array[i]);
 
 printf("n");

void print_2d_array(int **array, int *col_sizes, int size)

 for (int i = 0; i < size; i++) 
 print_1d_array(array[i], col_sizes[i]);
 

int** create_solution_array(node_t *head, int ans_size, int **column_sizes)

 int **ans = (int**)malloc(sizeof(int*)*ans_size);

 node_t *iter;
 iter = head->next;
 int idx = 0;
 while(iter) 
 ans[idx] = iter->array;
 (*column_sizes)[idx] = iter->size;
 idx++;
 iter = iter->next;
 
 return ans;


void gen_powerset(int *num, int num_size, int idx, int cur_size, int *cur, node_t **iter_node, int *ans_size) 
 if (idx == num_size) 
 node_t *new_node = alloc_node();
 if (cur_size) 
 new_node->array = (int *) malloc(sizeof(int) * cur_size);
 new_node->size = cur_size ;
 memcpy(new_node->array, cur, cur_size*sizeof(int));
 
 (*iter_node)->next = new_node;
 *iter_node = new_node;
 (*ans_size)++;
 return;
 

 gen_powerset(num, num_size, idx + 1, cur_size, cur, iter_node, ans_size);
 *(cur + cur_size) = num[idx];
 gen_powerset(num, num_size, idx + 1, cur_size + 1, cur, iter_node, ans_size);


int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize) 
 node_t *head = alloc_node();
 node_t *iter = head;
 int *cur = (int*)malloc(sizeof(int)*numsSize);
 gen_powerset(nums, numsSize, 0, 0, cur, &iter, returnSize);
 return create_solution_array(head, *returnSize, columnSizes);



int main ()

 int *nums = (int*)malloc(sizeof(int)*SIZE);
 for (int i = 0; i < SIZE; i++) 
 nums[i] = i+1;
 
 int *col_sizes = (int*)malloc(sizeof(int)*SIZE);
 int ans_size;
 int ** ans = subsets(nums, SIZE, &col_sizes, &ans_size);
 print_2d_array(ans, col_sizes, ans_size);
 return 0;




c programming-challenge combinatorics depth-first-search




share|improve this question






















  • @Toby Speight Added problem description.
    – wispymisty
    Sep 7 at 13:25












up vote
9
down vote

favorite
1









up vote
9
down vote

favorite
1






1





I am solving another problem in leetcode.




Given a set, generate all the subsets of the set.



Input: [1,2,3]

Output: [ [3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],]




The solution is accepted but I would like to improve on my C coding style. I have created a node_t type to encapsulate the data related each subset. There could be less verbose ways to do this. Two popular methods of solving this problem seem to be:



  1. backtracking

  2. a subset equals to binary number ≤ n where n is element count.

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


typedef struct node_s 
 int *array;
 int size;
 struct node_s *next;
 node_t;

node_t* alloc_node()

 return (node_t*)malloc(sizeof(node_t));


void free_node(node_t *node)

 free(node);

#define SIZE 3

void print_one(int *one)

 printf("%d ", *one);

void print_1d_array(int *array, int size)

 for(int i = 0; i < size; i++) 
 print_one(&array[i]);
 
 printf("n");

void print_2d_array(int **array, int *col_sizes, int size)

 for (int i = 0; i < size; i++) 
 print_1d_array(array[i], col_sizes[i]);
 

int** create_solution_array(node_t *head, int ans_size, int **column_sizes)

 int **ans = (int**)malloc(sizeof(int*)*ans_size);

 node_t *iter;
 iter = head->next;
 int idx = 0;
 while(iter) 
 ans[idx] = iter->array;
 (*column_sizes)[idx] = iter->size;
 idx++;
 iter = iter->next;
 
 return ans;


void gen_powerset(int *num, int num_size, int idx, int cur_size, int *cur, node_t **iter_node, int *ans_size) 
 if (idx == num_size) 
 node_t *new_node = alloc_node();
 if (cur_size) 
 new_node->array = (int *) malloc(sizeof(int) * cur_size);
 new_node->size = cur_size ;
 memcpy(new_node->array, cur, cur_size*sizeof(int));
 
 (*iter_node)->next = new_node;
 *iter_node = new_node;
 (*ans_size)++;
 return;
 

 gen_powerset(num, num_size, idx + 1, cur_size, cur, iter_node, ans_size);
 *(cur + cur_size) = num[idx];
 gen_powerset(num, num_size, idx + 1, cur_size + 1, cur, iter_node, ans_size);


int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize) 
 node_t *head = alloc_node();
 node_t *iter = head;
 int *cur = (int*)malloc(sizeof(int)*numsSize);
 gen_powerset(nums, numsSize, 0, 0, cur, &iter, returnSize);
 return create_solution_array(head, *returnSize, columnSizes);



int main ()

 int *nums = (int*)malloc(sizeof(int)*SIZE);
 for (int i = 0; i < SIZE; i++) 
 nums[i] = i+1;
 
 int *col_sizes = (int*)malloc(sizeof(int)*SIZE);
 int ans_size;
 int ** ans = subsets(nums, SIZE, &col_sizes, &ans_size);
 print_2d_array(ans, col_sizes, ans_size);
 return 0;




c programming-challenge combinatorics depth-first-search




share|improve this question














I am solving another problem in leetcode.




Given a set, generate all the subsets of the set.



Input: [1,2,3]

Output: [ [3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],]




The solution is accepted but I would like to improve on my C coding style. I have created a node_t type to encapsulate the data related each subset. There could be less verbose ways to do this. Two popular methods of solving this problem seem to be:



  1. backtracking

  2. a subset equals to binary number ≤ n where n is element count.

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


typedef struct node_s 
 int *array;
 int size;
 struct node_s *next;
 node_t;

node_t* alloc_node()

 return (node_t*)malloc(sizeof(node_t));


void free_node(node_t *node)

 free(node);

#define SIZE 3

void print_one(int *one)

 printf("%d ", *one);

void print_1d_array(int *array, int size)

 for(int i = 0; i < size; i++) 
 print_one(&array[i]);
 
 printf("n");

void print_2d_array(int **array, int *col_sizes, int size)

 for (int i = 0; i < size; i++) 
 print_1d_array(array[i], col_sizes[i]);
 

int** create_solution_array(node_t *head, int ans_size, int **column_sizes)

 int **ans = (int**)malloc(sizeof(int*)*ans_size);

 node_t *iter;
 iter = head->next;
 int idx = 0;
 while(iter) 
 ans[idx] = iter->array;
 (*column_sizes)[idx] = iter->size;
 idx++;
 iter = iter->next;
 
 return ans;


void gen_powerset(int *num, int num_size, int idx, int cur_size, int *cur, node_t **iter_node, int *ans_size) 
 if (idx == num_size) 
 node_t *new_node = alloc_node();
 if (cur_size) 
 new_node->array = (int *) malloc(sizeof(int) * cur_size);
 new_node->size = cur_size ;
 memcpy(new_node->array, cur, cur_size*sizeof(int));
 
 (*iter_node)->next = new_node;
 *iter_node = new_node;
 (*ans_size)++;
 return;
 

 gen_powerset(num, num_size, idx + 1, cur_size, cur, iter_node, ans_size);
 *(cur + cur_size) = num[idx];
 gen_powerset(num, num_size, idx + 1, cur_size + 1, cur, iter_node, ans_size);


int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize) 
 node_t *head = alloc_node();
 node_t *iter = head;
 int *cur = (int*)malloc(sizeof(int)*numsSize);
 gen_powerset(nums, numsSize, 0, 0, cur, &iter, returnSize);
 return create_solution_array(head, *returnSize, columnSizes);



int main ()

 int *nums = (int*)malloc(sizeof(int)*SIZE);
 for (int i = 0; i < SIZE; i++) 
 nums[i] = i+1;
 
 int *col_sizes = (int*)malloc(sizeof(int)*SIZE);
 int ans_size;
 int ** ans = subsets(nums, SIZE, &col_sizes, &ans_size);
 print_2d_array(ans, col_sizes, ans_size);
 return 0;





c programming-challenge combinatorics depth-first-search





share|improve this question













share|improve this question




share|improve this question








edited Sep 7 at 16:36









200_success

124k14144401




124k14144401










asked Sep 7 at 12:53









wispymisty

582




582











  • @Toby Speight Added problem description.
    – wispymisty
    Sep 7 at 13:25
















  • @Toby Speight Added problem description.
    – wispymisty
    Sep 7 at 13:25















@Toby Speight Added problem description.
– wispymisty
Sep 7 at 13:25




@Toby Speight Added problem description.
– wispymisty
Sep 7 at 13:25










2 Answers
2






active

oldest

votes

















up vote
7
down vote













I'll just work through this from the top:




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



Looks good; we need these.




typedef struct node_s 
 int *array;
 int size;
 struct node_s *next;
 node_t;



It's usual to use the same structure tag as the typename we're going to use: struct node_t.



If size is the number of elements in the array, a more natural type might be size_t.




node_t* alloc_node()

 return (node_t*)malloc(sizeof(node_t));




All this does is to allocate the memory. Consider initialising the members to sane values, too:



node_t* alloc_node()

 node_t *n = malloc(sizeof *n);
 if (n) 
 n->array = NULL;
 n->size = 0;
 n->next = NULL;
 
 return n;



We're writing C, so it's not advised to cast the result of malloc(). But we can't assume it succeeds!



It's a good habit to use the assigned-to variable in the argument of sizeof, rather than its type; that saves us the mental work of having to check that the type actually matches. That's why I've used sizeof *n in place of sizeof (node_t) here; you'll see just following an example where we're further from the declaration and this idiom has more benefit.



It's possibly a good idea to create the array at the same time:



node_t* alloc_node(size_t array_count)

 node_t *n = malloc(sizeof *n);
 if (n) 
 n->array = malloc(sizeof *n->array * array_count);
 n->size = n->array ? array_count : 0;
 n->next = NULL;
 
 return n;




void free_node(node_t *node)

 free(node);




Assuming that the node owns its array, we need to free that, too:



void free_node(node_t *node)

 if (node) 
 free(node->array);
 
 free(node);



Does the node own its next as well? If so, we need to free that, or perhaps return it.




#define SIZE 3



Why is this in the middle here? It should be right at the beginning (or perhaps just before main()).




void print_one(int *one)

 printf("%d ", *one);




I'm not convinced there's much benefit to encapsulating this as a function.




void print_1d_array(int *array, int size)

 for(int i = 0; i < size; i++) 
 print_one(&array[i]);
 
 printf("n");




We should use size_t for the count here:



void print_1d_array(int *array, size_t size)

 for (size_t i = 0; i < size; ++i) 
 printf("%d ", array[i]);
 
 printf("n");




void print_2d_array(int **array, int *col_sizes, int size)

 for (int i = 0; i < size; i++) 
 print_1d_array(array[i], col_sizes[i]);




Another size_t (okay, I'll stop mentioning these now).




int** create_solution_array(node_t *head, int ans_size, int **column_sizes)

 int **ans = (int**)malloc(sizeof(int*)*ans_size);

 node_t *iter;
 iter = head->next;
 int idx = 0;
 while(iter) 
 ans[idx] = iter->array;
 (*column_sizes)[idx] = iter->size;
 idx++;
 iter = iter->next;
 
 return ans;




Aside from points from earlier, that while loop has an initialisation and an advancement, so it's really a for loop:



int** create_solution_array(node_t *head, size_t ans_size, size_t **column_sizes)

 int **ans = malloc(sizeof *ans * ans_size);

 if (ans) 
 int idx = 0;
 for (node_t *iter = head->next; iter; iter = iter->next) 
 ans[idx] = iter->array;
 (*column_sizes)[idx] = iter->size;
 ++idx;
 
 
 return ans;




void gen_powerset(int *num, int num_size, int idx, int cur_size, int *cur, node_t **iter_node, int *ans_size) 
 if (idx == num_size) 
 node_t *new_node = alloc_node();
 if (cur_size) 
 new_node->array = (int *) malloc(sizeof(int) * cur_size);
 new_node->size = cur_size ;
 memcpy(new_node->array, cur, cur_size*sizeof(int));
 
 (*iter_node)->next = new_node;
 *iter_node = new_node;
 (*ans_size)++;
 return;
 

 gen_powerset(num, num_size, idx + 1, cur_size, cur, iter_node, ans_size);
 *(cur + cur_size) = num[idx];
 gen_powerset(num, num_size, idx + 1, cur_size + 1, cur, iter_node, ans_size);




*(cur + cur_size) is normally written cur[cur_size].



We need to check whether our allocations succeeded:



/* true if successful, false on any error (e.g. out of memory) */
bool gen_powerset(int *num, size_t num_size, size_t idx,
 size_t cur_size, int *cur, node_t **iter_node,
 size_t *ans_size)

 if (idx == num_size) 
 node_t *new_node = alloc_node(cur_size);
 if (!new_node 

 cur[cur_size] = num[idx];

 return gen_powerset(num, num_size, idx + 1, cur_size, cur, iter_node, ans_size)
 && gen_powerset(num, num_size, idx + 1, cur_size + 1, cur, iter_node, ans_size);




int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize) 
 node_t *head = alloc_node();
 node_t *iter = head;
 int *cur = (int*)malloc(sizeof(int)*numsSize);
 gen_powerset(nums, numsSize, 0, 0, cur, &iter, returnSize);
 return create_solution_array(head, *returnSize, columnSizes);




Again, check that malloc() succeeded, and check that gen_powerset() succeeded.




int main ()

 int *nums = (int*)malloc(sizeof(int)*SIZE);
 for (int i = 0; i < SIZE; i++) 
 nums[i] = i+1;
 
 int *col_sizes = (int*)malloc(sizeof(int)*SIZE);
 int ans_size;
 int ** ans = subsets(nums, SIZE, &col_sizes, &ans_size);
 print_2d_array(ans, col_sizes, ans_size);
 return 0;




Having carefully created free_node(), we completely forgot to use it. Valgrind reveals a substantial leak due to this. We need to free the other allocated memory, too.






share|improve this answer




















  • Thanks @Toby Speight, I am rewriting the solutions with your pointers in mind and comparing how close. I have come across most of the points that you have mentioned but, in practice, they didn't come out in force. I think it will be help to slow down a bit and savor every line I write.
    – wispymisty
    Sep 7 at 18:58

















up vote
5
down vote













I subscribe to everything @TobySpeight said.



I also believe that you could make your code a lot clearer (and your coding style better) by obeying a few important rules:



When in doubt, choose the simplest algorithm



Binary representation of numbers between 0 and the size of the powerset are the simplest tool to compute the subsets of the powerset; 0 means the absence, 1 the presence of an element of the initial set:



// 1, 2, 3
// 000 -> 
// 001 -> 3
// 010 -> 2
// ...
// 111 -> 1,2,3


Since the size of the powerset is 2^N, where N is the cardinality of the set, and given a function taking the original set and a number to return the subset characterized by this number, a simple array and a simple for loop are enough to achieve our objective:



for (int i = 0; i < pow(2, set.size); ++i)
 powerset[i] = subset(set, i);


That is quite simpler than linked nodes etc.



When in doubt, bundle together what goes together well



Outside of special cases, like the C-string, a pointer without a size won't be of much use to represent a range. So keep the pointer and the size together, rather than having arrays of pointers and arrays of sizes side by side, as in your subsets function:



typedef struct 
 int* items;
 size_t size;
 Set;

typedef struct 
 Set* subsets;
 size_t size;
 Powerset;


Whether you want to fill them, print them, free them, you'll need to have both informations, because you can't deduce one from the other.



A working example:



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

typedef struct 
 int* items;
 size_t size;
 Set;

typedef struct 
 Set* subsets;
 size_t size;
 Powerset;

int is_bit_on(int n, int pos) 
 return (n >> pos) & 1;


int set_bits(int n) 
 // any set bits counting function will do fine
 // this one is gcc only
 return __builtin_popcount(n);
 // but you could have to write your own;
 // see https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer


Set subset(Set set, int step) 
 int* subset = malloc(sizeof(int) * set_bits(step));
 if (subset == NULL) 
 Set failure = .items = NULL, .size = 0 ;
 return failure;
 
 int elem_n = 0;
 for (; set.size > 0; --set.size) 
 if (is_bit_on(step, set.size - 1))
 subset[elem_n++] = set.items[set.size-1];
 
 Set ret = .items = subset, .size = elem_n ;
 return ret;


Powerset powerset(Set set) 
 size_t powerset_size = pow(2, set.size);
 Powerset powerset = 
 .subsets = malloc(sizeof(Set) * powerset_size),
 .size = powerset_size
 ;
 Powerset failure = .subsets = NULL, .size = 0 ;
 if (powerset.subsets == NULL) return failure;

 for (size_t i = 0; i < powerset_size; ++i) 
 powerset.subsets[i] = subset(set, i);
 if (powerset.subsets[i].items == NULL) 
 for (size_t j = 0; j < i; ++j) 
 free(powerset.subsets[j].items);
 
 return failure;
 
 
 return powerset;


void free_powerset(Powerset powerset) 
 for (size_t i = 0; i < powerset.size; ++i) 
 free(powerset.subsets[i].items);
 
 free(powerset.subsets);


void print_array(Set array) 
 for (size_t i = 0; i < array.size; ++i)
 printf("%d, ", array.items[i]);
 printf("n");



int main(void) 
 int items = 1, 2, 3; 
 Set set = .items = items, .size = 3;
 Powerset test = powerset(set);

 if (test.subsets == NULL) 
 printf("Bad allocation");
 return 1;
 

 for (size_t i = 0; i < test.size; ++i)
 print_array(test.subsets[i]);

 free_powerset(test);
 return 0;






share|improve this answer




















  • Good solution, but it’s worth noting that it’s limited to sets no larger than the size of an int.
    – Edward
    Sep 7 at 16:05










  • @Edward Indeed, but this is an acceptable limitation since a set of 32 elements already has a power set of 2^32 elements, i.e more than 4 billions elements, which would take a good time to print...
    – papagaga
    Sep 7 at 16:09










  • Thanks papagaga. I have less experience using builtin functions. I think it is better to use those as they are fully blessed by relevant compilers ? I also like the fact that you are using inline struct initialization. That is really convenient and descriptive. Need to have an arsenal of "when-in-doubt" techniques ingrained in me. Yesterday, I was thinking of how to do inline initialization of function pointer or action based on a type field in type hierarchy. Just want to add some form of reflections with minimal effort. Thanks again for your answer. I will also subscribe to @Toby Speight.
    – wispymisty
    Sep 7 at 19:07










  • If you wanted to deal with sets containing more than 15 elements (where did you get 32 from?), then you could use one of the fixed-size unsigned types from <stdint.h>, of course.
    – Toby Speight
    2 days ago










Your Answer




StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "196"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);













 

draft saved


draft discarded


















StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f203305%2fgenerating-the-powerset-in-c%23new-answer', 'question_page');

);

Post as a guest

















2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
7
down vote













I'll just work through this from the top:




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



Looks good; we need these.




typedef struct node_s 
 int *array;
 int size;
 struct node_s *next;
 node_t;



It's usual to use the same structure tag as the typename we're going to use: struct node_t.



If size is the number of elements in the array, a more natural type might be size_t.




node_t* alloc_node()

 return (node_t*)malloc(sizeof(node_t));




All this does is to allocate the memory. Consider initialising the members to sane values, too:



node_t* alloc_node()

 node_t *n = malloc(sizeof *n);
 if (n) 
 n->array = NULL;
 n->size = 0;
 n->next = NULL;
 
 return n;



We're writing C, so it's not advised to cast the result of malloc(). But we can't assume it succeeds!



It's a good habit to use the assigned-to variable in the argument of sizeof, rather than its type; that saves us the mental work of having to check that the type actually matches. That's why I've used sizeof *n in place of sizeof (node_t) here; you'll see just following an example where we're further from the declaration and this idiom has more benefit.



It's possibly a good idea to create the array at the same time:



node_t* alloc_node(size_t array_count)

 node_t *n = malloc(sizeof *n);
 if (n) 
 n->array = malloc(sizeof *n->array * array_count);
 n->size = n->array ? array_count : 0;
 n->next = NULL;
 
 return n;




void free_node(node_t *node)

 free(node);




Assuming that the node owns its array, we need to free that, too:



void free_node(node_t *node)

 if (node) 
 free(node->array);
 
 free(node);



Does the node own its next as well? If so, we need to free that, or perhaps return it.




#define SIZE 3



Why is this in the middle here? It should be right at the beginning (or perhaps just before main()).




void print_one(int *one)

 printf("%d ", *one);




I'm not convinced there's much benefit to encapsulating this as a function.




void print_1d_array(int *array, int size)

 for(int i = 0; i < size; i++) 
 print_one(&array[i]);
 
 printf("n");




We should use size_t for the count here:



void print_1d_array(int *array, size_t size)

 for (size_t i = 0; i < size; ++i) 
 printf("%d ", array[i]);
 
 printf("n");




void print_2d_array(int **array, int *col_sizes, int size)

 for (int i = 0; i < size; i++) 
 print_1d_array(array[i], col_sizes[i]);




Another size_t (okay, I'll stop mentioning these now).




int** create_solution_array(node_t *head, int ans_size, int **column_sizes)

 int **ans = (int**)malloc(sizeof(int*)*ans_size);

 node_t *iter;
 iter = head->next;
 int idx = 0;
 while(iter) 
 ans[idx] = iter->array;
 (*column_sizes)[idx] = iter->size;
 idx++;
 iter = iter->next;
 
 return ans;




Aside from points from earlier, that while loop has an initialisation and an advancement, so it's really a for loop:



int** create_solution_array(node_t *head, size_t ans_size, size_t **column_sizes)

 int **ans = malloc(sizeof *ans * ans_size);

 if (ans) 
 int idx = 0;
 for (node_t *iter = head->next; iter; iter = iter->next) 
 ans[idx] = iter->array;
 (*column_sizes)[idx] = iter->size;
 ++idx;
 
 
 return ans;




void gen_powerset(int *num, int num_size, int idx, int cur_size, int *cur, node_t **iter_node, int *ans_size) 
 if (idx == num_size) 
 node_t *new_node = alloc_node();
 if (cur_size) 
 new_node->array = (int *) malloc(sizeof(int) * cur_size);
 new_node->size = cur_size ;
 memcpy(new_node->array, cur, cur_size*sizeof(int));
 
 (*iter_node)->next = new_node;
 *iter_node = new_node;
 (*ans_size)++;
 return;
 

 gen_powerset(num, num_size, idx + 1, cur_size, cur, iter_node, ans_size);
 *(cur + cur_size) = num[idx];
 gen_powerset(num, num_size, idx + 1, cur_size + 1, cur, iter_node, ans_size);




*(cur + cur_size) is normally written cur[cur_size].



We need to check whether our allocations succeeded:



/* true if successful, false on any error (e.g. out of memory) */
bool gen_powerset(int *num, size_t num_size, size_t idx,
 size_t cur_size, int *cur, node_t **iter_node,
 size_t *ans_size)

 if (idx == num_size) 
 node_t *new_node = alloc_node(cur_size);
 if (!new_node 

 cur[cur_size] = num[idx];

 return gen_powerset(num, num_size, idx + 1, cur_size, cur, iter_node, ans_size)
 && gen_powerset(num, num_size, idx + 1, cur_size + 1, cur, iter_node, ans_size);




int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize) 
 node_t *head = alloc_node();
 node_t *iter = head;
 int *cur = (int*)malloc(sizeof(int)*numsSize);
 gen_powerset(nums, numsSize, 0, 0, cur, &iter, returnSize);
 return create_solution_array(head, *returnSize, columnSizes);




Again, check that malloc() succeeded, and check that gen_powerset() succeeded.




int main ()

 int *nums = (int*)malloc(sizeof(int)*SIZE);
 for (int i = 0; i < SIZE; i++) 
 nums[i] = i+1;
 
 int *col_sizes = (int*)malloc(sizeof(int)*SIZE);
 int ans_size;
 int ** ans = subsets(nums, SIZE, &col_sizes, &ans_size);
 print_2d_array(ans, col_sizes, ans_size);
 return 0;




Having carefully created free_node(), we completely forgot to use it. Valgrind reveals a substantial leak due to this. We need to free the other allocated memory, too.






share|improve this answer




















  • Thanks @Toby Speight, I am rewriting the solutions with your pointers in mind and comparing how close. I have come across most of the points that you have mentioned but, in practice, they didn't come out in force. I think it will be help to slow down a bit and savor every line I write.
    – wispymisty
    Sep 7 at 18:58














up vote
7
down vote













I'll just work through this from the top:




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



Looks good; we need these.




typedef struct node_s 
 int *array;
 int size;
 struct node_s *next;
 node_t;



It's usual to use the same structure tag as the typename we're going to use: struct node_t.



If size is the number of elements in the array, a more natural type might be size_t.




node_t* alloc_node()

 return (node_t*)malloc(sizeof(node_t));




All this does is to allocate the memory. Consider initialising the members to sane values, too:



node_t* alloc_node()

 node_t *n = malloc(sizeof *n);
 if (n) 
 n->array = NULL;
 n->size = 0;
 n->next = NULL;
 
 return n;



We're writing C, so it's not advised to cast the result of malloc(). But we can't assume it succeeds!



It's a good habit to use the assigned-to variable in the argument of sizeof, rather than its type; that saves us the mental work of having to check that the type actually matches. That's why I've used sizeof *n in place of sizeof (node_t) here; you'll see just following an example where we're further from the declaration and this idiom has more benefit.



It's possibly a good idea to create the array at the same time:



node_t* alloc_node(size_t array_count)

 node_t *n = malloc(sizeof *n);
 if (n) 
 n->array = malloc(sizeof *n->array * array_count);
 n->size = n->array ? array_count : 0;
 n->next = NULL;
 
 return n;




void free_node(node_t *node)

 free(node);




Assuming that the node owns its array, we need to free that, too:



void free_node(node_t *node)

 if (node) 
 free(node->array);
 
 free(node);



Does the node own its next as well? If so, we need to free that, or perhaps return it.




#define SIZE 3



Why is this in the middle here? It should be right at the beginning (or perhaps just before main()).




void print_one(int *one)

 printf("%d ", *one);




I'm not convinced there's much benefit to encapsulating this as a function.




void print_1d_array(int *array, int size)

 for(int i = 0; i < size; i++) 
 print_one(&array[i]);
 
 printf("n");




We should use size_t for the count here:



void print_1d_array(int *array, size_t size)

 for (size_t i = 0; i < size; ++i) 
 printf("%d ", array[i]);
 
 printf("n");




void print_2d_array(int **array, int *col_sizes, int size)

 for (int i = 0; i < size; i++) 
 print_1d_array(array[i], col_sizes[i]);




Another size_t (okay, I'll stop mentioning these now).




int** create_solution_array(node_t *head, int ans_size, int **column_sizes)

 int **ans = (int**)malloc(sizeof(int*)*ans_size);

 node_t *iter;
 iter = head->next;
 int idx = 0;
 while(iter) 
 ans[idx] = iter->array;
 (*column_sizes)[idx] = iter->size;
 idx++;
 iter = iter->next;
 
 return ans;




Aside from points from earlier, that while loop has an initialisation and an advancement, so it's really a for loop:



int** create_solution_array(node_t *head, size_t ans_size, size_t **column_sizes)

 int **ans = malloc(sizeof *ans * ans_size);

 if (ans) 
 int idx = 0;
 for (node_t *iter = head->next; iter; iter = iter->next) 
 ans[idx] = iter->array;
 (*column_sizes)[idx] = iter->size;
 ++idx;
 
 
 return ans;




void gen_powerset(int *num, int num_size, int idx, int cur_size, int *cur, node_t **iter_node, int *ans_size) 
 if (idx == num_size) 
 node_t *new_node = alloc_node();
 if (cur_size) 
 new_node->array = (int *) malloc(sizeof(int) * cur_size);
 new_node->size = cur_size ;
 memcpy(new_node->array, cur, cur_size*sizeof(int));
 
 (*iter_node)->next = new_node;
 *iter_node = new_node;
 (*ans_size)++;
 return;
 

 gen_powerset(num, num_size, idx + 1, cur_size, cur, iter_node, ans_size);
 *(cur + cur_size) = num[idx];
 gen_powerset(num, num_size, idx + 1, cur_size + 1, cur, iter_node, ans_size);




*(cur + cur_size) is normally written cur[cur_size].



We need to check whether our allocations succeeded:



/* true if successful, false on any error (e.g. out of memory) */
bool gen_powerset(int *num, size_t num_size, size_t idx,
 size_t cur_size, int *cur, node_t **iter_node,
 size_t *ans_size)

 if (idx == num_size) 
 node_t *new_node = alloc_node(cur_size);
 if (!new_node 

 cur[cur_size] = num[idx];

 return gen_powerset(num, num_size, idx + 1, cur_size, cur, iter_node, ans_size)
 && gen_powerset(num, num_size, idx + 1, cur_size + 1, cur, iter_node, ans_size);




int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize) 
 node_t *head = alloc_node();
 node_t *iter = head;
 int *cur = (int*)malloc(sizeof(int)*numsSize);
 gen_powerset(nums, numsSize, 0, 0, cur, &iter, returnSize);
 return create_solution_array(head, *returnSize, columnSizes);




Again, check that malloc() succeeded, and check that gen_powerset() succeeded.




int main ()

 int *nums = (int*)malloc(sizeof(int)*SIZE);
 for (int i = 0; i < SIZE; i++) 
 nums[i] = i+1;
 
 int *col_sizes = (int*)malloc(sizeof(int)*SIZE);
 int ans_size;
 int ** ans = subsets(nums, SIZE, &col_sizes, &ans_size);
 print_2d_array(ans, col_sizes, ans_size);
 return 0;




Having carefully created free_node(), we completely forgot to use it. Valgrind reveals a substantial leak due to this. We need to free the other allocated memory, too.






share|improve this answer




















  • Thanks @Toby Speight, I am rewriting the solutions with your pointers in mind and comparing how close. I have come across most of the points that you have mentioned but, in practice, they didn't come out in force. I think it will be help to slow down a bit and savor every line I write.
    – wispymisty
    Sep 7 at 18:58












up vote
7
down vote










up vote
7
down vote









I'll just work through this from the top:




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



Looks good; we need these.




typedef struct node_s 
 int *array;
 int size;
 struct node_s *next;
 node_t;



It's usual to use the same structure tag as the typename we're going to use: struct node_t.



If size is the number of elements in the array, a more natural type might be size_t.




node_t* alloc_node()

 return (node_t*)malloc(sizeof(node_t));




All this does is to allocate the memory. Consider initialising the members to sane values, too:



node_t* alloc_node()

 node_t *n = malloc(sizeof *n);
 if (n) 
 n->array = NULL;
 n->size = 0;
 n->next = NULL;
 
 return n;



We're writing C, so it's not advised to cast the result of malloc(). But we can't assume it succeeds!



It's a good habit to use the assigned-to variable in the argument of sizeof, rather than its type; that saves us the mental work of having to check that the type actually matches. That's why I've used sizeof *n in place of sizeof (node_t) here; you'll see just following an example where we're further from the declaration and this idiom has more benefit.



It's possibly a good idea to create the array at the same time:



node_t* alloc_node(size_t array_count)

 node_t *n = malloc(sizeof *n);
 if (n) 
 n->array = malloc(sizeof *n->array * array_count);
 n->size = n->array ? array_count : 0;
 n->next = NULL;
 
 return n;




void free_node(node_t *node)

 free(node);




Assuming that the node owns its array, we need to free that, too:



void free_node(node_t *node)

 if (node) 
 free(node->array);
 
 free(node);



Does the node own its next as well? If so, we need to free that, or perhaps return it.




#define SIZE 3



Why is this in the middle here? It should be right at the beginning (or perhaps just before main()).




void print_one(int *one)

 printf("%d ", *one);




I'm not convinced there's much benefit to encapsulating this as a function.




void print_1d_array(int *array, int size)

 for(int i = 0; i < size; i++) 
 print_one(&array[i]);
 
 printf("n");




We should use size_t for the count here:



void print_1d_array(int *array, size_t size)

 for (size_t i = 0; i < size; ++i) 
 printf("%d ", array[i]);
 
 printf("n");




void print_2d_array(int **array, int *col_sizes, int size)

 for (int i = 0; i < size; i++) 
 print_1d_array(array[i], col_sizes[i]);




Another size_t (okay, I'll stop mentioning these now).




int** create_solution_array(node_t *head, int ans_size, int **column_sizes)

 int **ans = (int**)malloc(sizeof(int*)*ans_size);

 node_t *iter;
 iter = head->next;
 int idx = 0;
 while(iter) 
 ans[idx] = iter->array;
 (*column_sizes)[idx] = iter->size;
 idx++;
 iter = iter->next;
 
 return ans;




Aside from points from earlier, that while loop has an initialisation and an advancement, so it's really a for loop:



int** create_solution_array(node_t *head, size_t ans_size, size_t **column_sizes)

 int **ans = malloc(sizeof *ans * ans_size);

 if (ans) 
 int idx = 0;
 for (node_t *iter = head->next; iter; iter = iter->next) 
 ans[idx] = iter->array;
 (*column_sizes)[idx] = iter->size;
 ++idx;
 
 
 return ans;




void gen_powerset(int *num, int num_size, int idx, int cur_size, int *cur, node_t **iter_node, int *ans_size) 
 if (idx == num_size) 
 node_t *new_node = alloc_node();
 if (cur_size) 
 new_node->array = (int *) malloc(sizeof(int) * cur_size);
 new_node->size = cur_size ;
 memcpy(new_node->array, cur, cur_size*sizeof(int));
 
 (*iter_node)->next = new_node;
 *iter_node = new_node;
 (*ans_size)++;
 return;
 

 gen_powerset(num, num_size, idx + 1, cur_size, cur, iter_node, ans_size);
 *(cur + cur_size) = num[idx];
 gen_powerset(num, num_size, idx + 1, cur_size + 1, cur, iter_node, ans_size);




*(cur + cur_size) is normally written cur[cur_size].



We need to check whether our allocations succeeded:



/* true if successful, false on any error (e.g. out of memory) */
bool gen_powerset(int *num, size_t num_size, size_t idx,
 size_t cur_size, int *cur, node_t **iter_node,
 size_t *ans_size)

 if (idx == num_size) 
 node_t *new_node = alloc_node(cur_size);
 if (!new_node 

 cur[cur_size] = num[idx];

 return gen_powerset(num, num_size, idx + 1, cur_size, cur, iter_node, ans_size)
 && gen_powerset(num, num_size, idx + 1, cur_size + 1, cur, iter_node, ans_size);




int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize) 
 node_t *head = alloc_node();
 node_t *iter = head;
 int *cur = (int*)malloc(sizeof(int)*numsSize);
 gen_powerset(nums, numsSize, 0, 0, cur, &iter, returnSize);
 return create_solution_array(head, *returnSize, columnSizes);




Again, check that malloc() succeeded, and check that gen_powerset() succeeded.




int main ()

 int *nums = (int*)malloc(sizeof(int)*SIZE);
 for (int i = 0; i < SIZE; i++) 
 nums[i] = i+1;
 
 int *col_sizes = (int*)malloc(sizeof(int)*SIZE);
 int ans_size;
 int ** ans = subsets(nums, SIZE, &col_sizes, &ans_size);
 print_2d_array(ans, col_sizes, ans_size);
 return 0;




Having carefully created free_node(), we completely forgot to use it. Valgrind reveals a substantial leak due to this. We need to free the other allocated memory, too.






share|improve this answer












I'll just work through this from the top:




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



Looks good; we need these.




typedef struct node_s 
 int *array;
 int size;
 struct node_s *next;
 node_t;



It's usual to use the same structure tag as the typename we're going to use: struct node_t.



If size is the number of elements in the array, a more natural type might be size_t.




node_t* alloc_node()

 return (node_t*)malloc(sizeof(node_t));




All this does is to allocate the memory. Consider initialising the members to sane values, too:



node_t* alloc_node()

 node_t *n = malloc(sizeof *n);
 if (n) 
 n->array = NULL;
 n->size = 0;
 n->next = NULL;
 
 return n;



We're writing C, so it's not advised to cast the result of malloc(). But we can't assume it succeeds!



It's a good habit to use the assigned-to variable in the argument of sizeof, rather than its type; that saves us the mental work of having to check that the type actually matches. That's why I've used sizeof *n in place of sizeof (node_t) here; you'll see just following an example where we're further from the declaration and this idiom has more benefit.



It's possibly a good idea to create the array at the same time:



node_t* alloc_node(size_t array_count)

 node_t *n = malloc(sizeof *n);
 if (n) 
 n->array = malloc(sizeof *n->array * array_count);
 n->size = n->array ? array_count : 0;
 n->next = NULL;
 
 return n;




void free_node(node_t *node)

 free(node);




Assuming that the node owns its array, we need to free that, too:



void free_node(node_t *node)

 if (node) 
 free(node->array);
 
 free(node);



Does the node own its next as well? If so, we need to free that, or perhaps return it.




#define SIZE 3



Why is this in the middle here? It should be right at the beginning (or perhaps just before main()).




void print_one(int *one)

 printf("%d ", *one);




I'm not convinced there's much benefit to encapsulating this as a function.




void print_1d_array(int *array, int size)

 for(int i = 0; i < size; i++) 
 print_one(&array[i]);
 
 printf("n");




We should use size_t for the count here:



void print_1d_array(int *array, size_t size)

 for (size_t i = 0; i < size; ++i) 
 printf("%d ", array[i]);
 
 printf("n");




void print_2d_array(int **array, int *col_sizes, int size)

 for (int i = 0; i < size; i++) 
 print_1d_array(array[i], col_sizes[i]);




Another size_t (okay, I'll stop mentioning these now).




int** create_solution_array(node_t *head, int ans_size, int **column_sizes)

 int **ans = (int**)malloc(sizeof(int*)*ans_size);

 node_t *iter;
 iter = head->next;
 int idx = 0;
 while(iter) 
 ans[idx] = iter->array;
 (*column_sizes)[idx] = iter->size;
 idx++;
 iter = iter->next;
 
 return ans;




Aside from points from earlier, that while loop has an initialisation and an advancement, so it's really a for loop:



int** create_solution_array(node_t *head, size_t ans_size, size_t **column_sizes)

 int **ans = malloc(sizeof *ans * ans_size);

 if (ans) 
 int idx = 0;
 for (node_t *iter = head->next; iter; iter = iter->next) 
 ans[idx] = iter->array;
 (*column_sizes)[idx] = iter->size;
 ++idx;
 
 
 return ans;




void gen_powerset(int *num, int num_size, int idx, int cur_size, int *cur, node_t **iter_node, int *ans_size) 
 if (idx == num_size) 
 node_t *new_node = alloc_node();
 if (cur_size) 
 new_node->array = (int *) malloc(sizeof(int) * cur_size);
 new_node->size = cur_size ;
 memcpy(new_node->array, cur, cur_size*sizeof(int));
 
 (*iter_node)->next = new_node;
 *iter_node = new_node;
 (*ans_size)++;
 return;
 

 gen_powerset(num, num_size, idx + 1, cur_size, cur, iter_node, ans_size);
 *(cur + cur_size) = num[idx];
 gen_powerset(num, num_size, idx + 1, cur_size + 1, cur, iter_node, ans_size);




*(cur + cur_size) is normally written cur[cur_size].



We need to check whether our allocations succeeded:



/* true if successful, false on any error (e.g. out of memory) */
bool gen_powerset(int *num, size_t num_size, size_t idx,
 size_t cur_size, int *cur, node_t **iter_node,
 size_t *ans_size)

 if (idx == num_size) 
 node_t *new_node = alloc_node(cur_size);
 if (!new_node 

 cur[cur_size] = num[idx];

 return gen_powerset(num, num_size, idx + 1, cur_size, cur, iter_node, ans_size)
 && gen_powerset(num, num_size, idx + 1, cur_size + 1, cur, iter_node, ans_size);




int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize) 
 node_t *head = alloc_node();
 node_t *iter = head;
 int *cur = (int*)malloc(sizeof(int)*numsSize);
 gen_powerset(nums, numsSize, 0, 0, cur, &iter, returnSize);
 return create_solution_array(head, *returnSize, columnSizes);




Again, check that malloc() succeeded, and check that gen_powerset() succeeded.




int main ()

 int *nums = (int*)malloc(sizeof(int)*SIZE);
 for (int i = 0; i < SIZE; i++) 
 nums[i] = i+1;
 
 int *col_sizes = (int*)malloc(sizeof(int)*SIZE);
 int ans_size;
 int ** ans = subsets(nums, SIZE, &col_sizes, &ans_size);
 print_2d_array(ans, col_sizes, ans_size);
 return 0;




Having carefully created free_node(), we completely forgot to use it. Valgrind reveals a substantial leak due to this. We need to free the other allocated memory, too.







share|improve this answer












share|improve this answer



share|improve this answer










answered Sep 7 at 14:22









Toby Speight

18.7k23695




18.7k23695











  • Thanks @Toby Speight, I am rewriting the solutions with your pointers in mind and comparing how close. I have come across most of the points that you have mentioned but, in practice, they didn't come out in force. I think it will be help to slow down a bit and savor every line I write.
    – wispymisty
    Sep 7 at 18:58
















  • Thanks @Toby Speight, I am rewriting the solutions with your pointers in mind and comparing how close. I have come across most of the points that you have mentioned but, in practice, they didn't come out in force. I think it will be help to slow down a bit and savor every line I write.
    – wispymisty
    Sep 7 at 18:58















Thanks @Toby Speight, I am rewriting the solutions with your pointers in mind and comparing how close. I have come across most of the points that you have mentioned but, in practice, they didn't come out in force. I think it will be help to slow down a bit and savor every line I write.
– wispymisty
Sep 7 at 18:58




Thanks @Toby Speight, I am rewriting the solutions with your pointers in mind and comparing how close. I have come across most of the points that you have mentioned but, in practice, they didn't come out in force. I think it will be help to slow down a bit and savor every line I write.
– wispymisty
Sep 7 at 18:58












up vote
5
down vote













I subscribe to everything @TobySpeight said.



I also believe that you could make your code a lot clearer (and your coding style better) by obeying a few important rules:



When in doubt, choose the simplest algorithm



Binary representation of numbers between 0 and the size of the powerset are the simplest tool to compute the subsets of the powerset; 0 means the absence, 1 the presence of an element of the initial set:



// 1, 2, 3
// 000 -> 
// 001 -> 3
// 010 -> 2
// ...
// 111 -> 1,2,3


Since the size of the powerset is 2^N, where N is the cardinality of the set, and given a function taking the original set and a number to return the subset characterized by this number, a simple array and a simple for loop are enough to achieve our objective:



for (int i = 0; i < pow(2, set.size); ++i)
 powerset[i] = subset(set, i);


That is quite simpler than linked nodes etc.



When in doubt, bundle together what goes together well



Outside of special cases, like the C-string, a pointer without a size won't be of much use to represent a range. So keep the pointer and the size together, rather than having arrays of pointers and arrays of sizes side by side, as in your subsets function:



typedef struct 
 int* items;
 size_t size;
 Set;

typedef struct 
 Set* subsets;
 size_t size;
 Powerset;


Whether you want to fill them, print them, free them, you'll need to have both informations, because you can't deduce one from the other.



A working example:



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

typedef struct 
 int* items;
 size_t size;
 Set;

typedef struct 
 Set* subsets;
 size_t size;
 Powerset;

int is_bit_on(int n, int pos) 
 return (n >> pos) & 1;


int set_bits(int n) 
 // any set bits counting function will do fine
 // this one is gcc only
 return __builtin_popcount(n);
 // but you could have to write your own;
 // see https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer


Set subset(Set set, int step) 
 int* subset = malloc(sizeof(int) * set_bits(step));
 if (subset == NULL) 
 Set failure = .items = NULL, .size = 0 ;
 return failure;
 
 int elem_n = 0;
 for (; set.size > 0; --set.size) 
 if (is_bit_on(step, set.size - 1))
 subset[elem_n++] = set.items[set.size-1];
 
 Set ret = .items = subset, .size = elem_n ;
 return ret;


Powerset powerset(Set set) 
 size_t powerset_size = pow(2, set.size);
 Powerset powerset = 
 .subsets = malloc(sizeof(Set) * powerset_size),
 .size = powerset_size
 ;
 Powerset failure = .subsets = NULL, .size = 0 ;
 if (powerset.subsets == NULL) return failure;

 for (size_t i = 0; i < powerset_size; ++i) 
 powerset.subsets[i] = subset(set, i);
 if (powerset.subsets[i].items == NULL) 
 for (size_t j = 0; j < i; ++j) 
 free(powerset.subsets[j].items);
 
 return failure;
 
 
 return powerset;


void free_powerset(Powerset powerset) 
 for (size_t i = 0; i < powerset.size; ++i) 
 free(powerset.subsets[i].items);
 
 free(powerset.subsets);


void print_array(Set array) 
 for (size_t i = 0; i < array.size; ++i)
 printf("%d, ", array.items[i]);
 printf("n");



int main(void) 
 int items = 1, 2, 3; 
 Set set = .items = items, .size = 3;
 Powerset test = powerset(set);

 if (test.subsets == NULL) 
 printf("Bad allocation");
 return 1;
 

 for (size_t i = 0; i < test.size; ++i)
 print_array(test.subsets[i]);

 free_powerset(test);
 return 0;






share|improve this answer




















  • Good solution, but it’s worth noting that it’s limited to sets no larger than the size of an int.
    – Edward
    Sep 7 at 16:05










  • @Edward Indeed, but this is an acceptable limitation since a set of 32 elements already has a power set of 2^32 elements, i.e more than 4 billions elements, which would take a good time to print...
    – papagaga
    Sep 7 at 16:09










  • Thanks papagaga. I have less experience using builtin functions. I think it is better to use those as they are fully blessed by relevant compilers ? I also like the fact that you are using inline struct initialization. That is really convenient and descriptive. Need to have an arsenal of "when-in-doubt" techniques ingrained in me. Yesterday, I was thinking of how to do inline initialization of function pointer or action based on a type field in type hierarchy. Just want to add some form of reflections with minimal effort. Thanks again for your answer. I will also subscribe to @Toby Speight.
    – wispymisty
    Sep 7 at 19:07










  • If you wanted to deal with sets containing more than 15 elements (where did you get 32 from?), then you could use one of the fixed-size unsigned types from <stdint.h>, of course.
    – Toby Speight
    2 days ago














up vote
5
down vote













I subscribe to everything @TobySpeight said.



I also believe that you could make your code a lot clearer (and your coding style better) by obeying a few important rules:



When in doubt, choose the simplest algorithm



Binary representation of numbers between 0 and the size of the powerset are the simplest tool to compute the subsets of the powerset; 0 means the absence, 1 the presence of an element of the initial set:



// 1, 2, 3
// 000 -> 
// 001 -> 3
// 010 -> 2
// ...
// 111 -> 1,2,3


Since the size of the powerset is 2^N, where N is the cardinality of the set, and given a function taking the original set and a number to return the subset characterized by this number, a simple array and a simple for loop are enough to achieve our objective:



for (int i = 0; i < pow(2, set.size); ++i)
 powerset[i] = subset(set, i);


That is quite simpler than linked nodes etc.



When in doubt, bundle together what goes together well



Outside of special cases, like the C-string, a pointer without a size won't be of much use to represent a range. So keep the pointer and the size together, rather than having arrays of pointers and arrays of sizes side by side, as in your subsets function:



typedef struct 
 int* items;
 size_t size;
 Set;

typedef struct 
 Set* subsets;
 size_t size;
 Powerset;


Whether you want to fill them, print them, free them, you'll need to have both informations, because you can't deduce one from the other.



A working example:



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

typedef struct 
 int* items;
 size_t size;
 Set;

typedef struct 
 Set* subsets;
 size_t size;
 Powerset;

int is_bit_on(int n, int pos) 
 return (n >> pos) & 1;


int set_bits(int n) 
 // any set bits counting function will do fine
 // this one is gcc only
 return __builtin_popcount(n);
 // but you could have to write your own;
 // see https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer


Set subset(Set set, int step) 
 int* subset = malloc(sizeof(int) * set_bits(step));
 if (subset == NULL) 
 Set failure = .items = NULL, .size = 0 ;
 return failure;
 
 int elem_n = 0;
 for (; set.size > 0; --set.size) 
 if (is_bit_on(step, set.size - 1))
 subset[elem_n++] = set.items[set.size-1];
 
 Set ret = .items = subset, .size = elem_n ;
 return ret;


Powerset powerset(Set set) 
 size_t powerset_size = pow(2, set.size);
 Powerset powerset = 
 .subsets = malloc(sizeof(Set) * powerset_size),
 .size = powerset_size
 ;
 Powerset failure = .subsets = NULL, .size = 0 ;
 if (powerset.subsets == NULL) return failure;

 for (size_t i = 0; i < powerset_size; ++i) 
 powerset.subsets[i] = subset(set, i);
 if (powerset.subsets[i].items == NULL) 
 for (size_t j = 0; j < i; ++j) 
 free(powerset.subsets[j].items);
 
 return failure;
 
 
 return powerset;


void free_powerset(Powerset powerset) 
 for (size_t i = 0; i < powerset.size; ++i) 
 free(powerset.subsets[i].items);
 
 free(powerset.subsets);


void print_array(Set array) 
 for (size_t i = 0; i < array.size; ++i)
 printf("%d, ", array.items[i]);
 printf("n");



int main(void) 
 int items = 1, 2, 3; 
 Set set = .items = items, .size = 3;
 Powerset test = powerset(set);

 if (test.subsets == NULL) 
 printf("Bad allocation");
 return 1;
 

 for (size_t i = 0; i < test.size; ++i)
 print_array(test.subsets[i]);

 free_powerset(test);
 return 0;






share|improve this answer




















  • Good solution, but it’s worth noting that it’s limited to sets no larger than the size of an int.
    – Edward
    Sep 7 at 16:05










  • @Edward Indeed, but this is an acceptable limitation since a set of 32 elements already has a power set of 2^32 elements, i.e more than 4 billions elements, which would take a good time to print...
    – papagaga
    Sep 7 at 16:09










  • Thanks papagaga. I have less experience using builtin functions. I think it is better to use those as they are fully blessed by relevant compilers ? I also like the fact that you are using inline struct initialization. That is really convenient and descriptive. Need to have an arsenal of "when-in-doubt" techniques ingrained in me. Yesterday, I was thinking of how to do inline initialization of function pointer or action based on a type field in type hierarchy. Just want to add some form of reflections with minimal effort. Thanks again for your answer. I will also subscribe to @Toby Speight.
    – wispymisty
    Sep 7 at 19:07










  • If you wanted to deal with sets containing more than 15 elements (where did you get 32 from?), then you could use one of the fixed-size unsigned types from <stdint.h>, of course.
    – Toby Speight
    2 days ago












up vote
5
down vote










up vote
5
down vote









I subscribe to everything @TobySpeight said.



I also believe that you could make your code a lot clearer (and your coding style better) by obeying a few important rules:



When in doubt, choose the simplest algorithm



Binary representation of numbers between 0 and the size of the powerset are the simplest tool to compute the subsets of the powerset; 0 means the absence, 1 the presence of an element of the initial set:



// 1, 2, 3
// 000 -> 
// 001 -> 3
// 010 -> 2
// ...
// 111 -> 1,2,3


Since the size of the powerset is 2^N, where N is the cardinality of the set, and given a function taking the original set and a number to return the subset characterized by this number, a simple array and a simple for loop are enough to achieve our objective:



for (int i = 0; i < pow(2, set.size); ++i)
 powerset[i] = subset(set, i);


That is quite simpler than linked nodes etc.



When in doubt, bundle together what goes together well



Outside of special cases, like the C-string, a pointer without a size won't be of much use to represent a range. So keep the pointer and the size together, rather than having arrays of pointers and arrays of sizes side by side, as in your subsets function:



typedef struct 
 int* items;
 size_t size;
 Set;

typedef struct 
 Set* subsets;
 size_t size;
 Powerset;


Whether you want to fill them, print them, free them, you'll need to have both informations, because you can't deduce one from the other.



A working example:



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

typedef struct 
 int* items;
 size_t size;
 Set;

typedef struct 
 Set* subsets;
 size_t size;
 Powerset;

int is_bit_on(int n, int pos) 
 return (n >> pos) & 1;


int set_bits(int n) 
 // any set bits counting function will do fine
 // this one is gcc only
 return __builtin_popcount(n);
 // but you could have to write your own;
 // see https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer


Set subset(Set set, int step) 
 int* subset = malloc(sizeof(int) * set_bits(step));
 if (subset == NULL) 
 Set failure = .items = NULL, .size = 0 ;
 return failure;
 
 int elem_n = 0;
 for (; set.size > 0; --set.size) 
 if (is_bit_on(step, set.size - 1))
 subset[elem_n++] = set.items[set.size-1];
 
 Set ret = .items = subset, .size = elem_n ;
 return ret;


Powerset powerset(Set set) 
 size_t powerset_size = pow(2, set.size);
 Powerset powerset = 
 .subsets = malloc(sizeof(Set) * powerset_size),
 .size = powerset_size
 ;
 Powerset failure = .subsets = NULL, .size = 0 ;
 if (powerset.subsets == NULL) return failure;

 for (size_t i = 0; i < powerset_size; ++i) 
 powerset.subsets[i] = subset(set, i);
 if (powerset.subsets[i].items == NULL) 
 for (size_t j = 0; j < i; ++j) 
 free(powerset.subsets[j].items);
 
 return failure;
 
 
 return powerset;


void free_powerset(Powerset powerset) 
 for (size_t i = 0; i < powerset.size; ++i) 
 free(powerset.subsets[i].items);
 
 free(powerset.subsets);


void print_array(Set array) 
 for (size_t i = 0; i < array.size; ++i)
 printf("%d, ", array.items[i]);
 printf("n");



int main(void) 
 int items = 1, 2, 3; 
 Set set = .items = items, .size = 3;
 Powerset test = powerset(set);

 if (test.subsets == NULL) 
 printf("Bad allocation");
 return 1;
 

 for (size_t i = 0; i < test.size; ++i)
 print_array(test.subsets[i]);

 free_powerset(test);
 return 0;






share|improve this answer












I subscribe to everything @TobySpeight said.



I also believe that you could make your code a lot clearer (and your coding style better) by obeying a few important rules:



When in doubt, choose the simplest algorithm



Binary representation of numbers between 0 and the size of the powerset are the simplest tool to compute the subsets of the powerset; 0 means the absence, 1 the presence of an element of the initial set:



// 1, 2, 3
// 000 -> 
// 001 -> 3
// 010 -> 2
// ...
// 111 -> 1,2,3


Since the size of the powerset is 2^N, where N is the cardinality of the set, and given a function taking the original set and a number to return the subset characterized by this number, a simple array and a simple for loop are enough to achieve our objective:



for (int i = 0; i < pow(2, set.size); ++i)
 powerset[i] = subset(set, i);


That is quite simpler than linked nodes etc.



When in doubt, bundle together what goes together well



Outside of special cases, like the C-string, a pointer without a size won't be of much use to represent a range. So keep the pointer and the size together, rather than having arrays of pointers and arrays of sizes side by side, as in your subsets function:



typedef struct 
 int* items;
 size_t size;
 Set;

typedef struct 
 Set* subsets;
 size_t size;
 Powerset;


Whether you want to fill them, print them, free them, you'll need to have both informations, because you can't deduce one from the other.



A working example:



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

typedef struct 
 int* items;
 size_t size;
 Set;

typedef struct 
 Set* subsets;
 size_t size;
 Powerset;

int is_bit_on(int n, int pos) 
 return (n >> pos) & 1;


int set_bits(int n) 
 // any set bits counting function will do fine
 // this one is gcc only
 return __builtin_popcount(n);
 // but you could have to write your own;
 // see https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer


Set subset(Set set, int step) 
 int* subset = malloc(sizeof(int) * set_bits(step));
 if (subset == NULL) 
 Set failure = .items = NULL, .size = 0 ;
 return failure;
 
 int elem_n = 0;
 for (; set.size > 0; --set.size) 
 if (is_bit_on(step, set.size - 1))
 subset[elem_n++] = set.items[set.size-1];
 
 Set ret = .items = subset, .size = elem_n ;
 return ret;


Powerset powerset(Set set) 
 size_t powerset_size = pow(2, set.size);
 Powerset powerset = 
 .subsets = malloc(sizeof(Set) * powerset_size),
 .size = powerset_size
 ;
 Powerset failure = .subsets = NULL, .size = 0 ;
 if (powerset.subsets == NULL) return failure;

 for (size_t i = 0; i < powerset_size; ++i) 
 powerset.subsets[i] = subset(set, i);
 if (powerset.subsets[i].items == NULL) 
 for (size_t j = 0; j < i; ++j) 
 free(powerset.subsets[j].items);
 
 return failure;
 
 
 return powerset;


void free_powerset(Powerset powerset) 
 for (size_t i = 0; i < powerset.size; ++i) 
 free(powerset.subsets[i].items);
 
 free(powerset.subsets);


void print_array(Set array) 
 for (size_t i = 0; i < array.size; ++i)
 printf("%d, ", array.items[i]);
 printf("n");



int main(void) 
 int items = 1, 2, 3; 
 Set set = .items = items, .size = 3;
 Powerset test = powerset(set);

 if (test.subsets == NULL) 
 printf("Bad allocation");
 return 1;
 

 for (size_t i = 0; i < test.size; ++i)
 print_array(test.subsets[i]);

 free_powerset(test);
 return 0;







share|improve this answer












share|improve this answer



share|improve this answer










answered Sep 7 at 15:32









papagaga

3,244217




3,244217











  • Good solution, but it’s worth noting that it’s limited to sets no larger than the size of an int.
    – Edward
    Sep 7 at 16:05










  • @Edward Indeed, but this is an acceptable limitation since a set of 32 elements already has a power set of 2^32 elements, i.e more than 4 billions elements, which would take a good time to print...
    – papagaga
    Sep 7 at 16:09










  • Thanks papagaga. I have less experience using builtin functions. I think it is better to use those as they are fully blessed by relevant compilers ? I also like the fact that you are using inline struct initialization. That is really convenient and descriptive. Need to have an arsenal of "when-in-doubt" techniques ingrained in me. Yesterday, I was thinking of how to do inline initialization of function pointer or action based on a type field in type hierarchy. Just want to add some form of reflections with minimal effort. Thanks again for your answer. I will also subscribe to @Toby Speight.
    – wispymisty
    Sep 7 at 19:07










  • If you wanted to deal with sets containing more than 15 elements (where did you get 32 from?), then you could use one of the fixed-size unsigned types from <stdint.h>, of course.
    – Toby Speight
    2 days ago
















  • Good solution, but it’s worth noting that it’s limited to sets no larger than the size of an int.
    – Edward
    Sep 7 at 16:05










  • @Edward Indeed, but this is an acceptable limitation since a set of 32 elements already has a power set of 2^32 elements, i.e more than 4 billions elements, which would take a good time to print...
    – papagaga
    Sep 7 at 16:09










  • Thanks papagaga. I have less experience using builtin functions. I think it is better to use those as they are fully blessed by relevant compilers ? I also like the fact that you are using inline struct initialization. That is really convenient and descriptive. Need to have an arsenal of "when-in-doubt" techniques ingrained in me. Yesterday, I was thinking of how to do inline initialization of function pointer or action based on a type field in type hierarchy. Just want to add some form of reflections with minimal effort. Thanks again for your answer. I will also subscribe to @Toby Speight.
    – wispymisty
    Sep 7 at 19:07










  • If you wanted to deal with sets containing more than 15 elements (where did you get 32 from?), then you could use one of the fixed-size unsigned types from <stdint.h>, of course.
    – Toby Speight
    2 days ago















Good solution, but it’s worth noting that it’s limited to sets no larger than the size of an int.
– Edward
Sep 7 at 16:05




Good solution, but it’s worth noting that it’s limited to sets no larger than the size of an int.
– Edward
Sep 7 at 16:05












@Edward Indeed, but this is an acceptable limitation since a set of 32 elements already has a power set of 2^32 elements, i.e more than 4 billions elements, which would take a good time to print...
– papagaga
Sep 7 at 16:09




@Edward Indeed, but this is an acceptable limitation since a set of 32 elements already has a power set of 2^32 elements, i.e more than 4 billions elements, which would take a good time to print...
– papagaga
Sep 7 at 16:09












Thanks papagaga. I have less experience using builtin functions. I think it is better to use those as they are fully blessed by relevant compilers ? I also like the fact that you are using inline struct initialization. That is really convenient and descriptive. Need to have an arsenal of "when-in-doubt" techniques ingrained in me. Yesterday, I was thinking of how to do inline initialization of function pointer or action based on a type field in type hierarchy. Just want to add some form of reflections with minimal effort. Thanks again for your answer. I will also subscribe to @Toby Speight.
– wispymisty
Sep 7 at 19:07




Thanks papagaga. I have less experience using builtin functions. I think it is better to use those as they are fully blessed by relevant compilers ? I also like the fact that you are using inline struct initialization. That is really convenient and descriptive. Need to have an arsenal of "when-in-doubt" techniques ingrained in me. Yesterday, I was thinking of how to do inline initialization of function pointer or action based on a type field in type hierarchy. Just want to add some form of reflections with minimal effort. Thanks again for your answer. I will also subscribe to @Toby Speight.
– wispymisty
Sep 7 at 19:07












If you wanted to deal with sets containing more than 15 elements (where did you get 32 from?), then you could use one of the fixed-size unsigned types from <stdint.h>, of course.
– Toby Speight
2 days ago




If you wanted to deal with sets containing more than 15 elements (where did you get 32 from?), then you could use one of the fixed-size unsigned types from <stdint.h>, of course.
– Toby Speight
2 days ago

















 

draft saved


draft discarded















































 


draft saved


draft discarded














StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f203305%2fgenerating-the-powerset-in-c%23new-answer', 'question_page');

);

Post as a guest
































































Comments

Post a Comment

Popular posts from this blog

What does second last employer means? [closed]

Image
Clash Royale CLAN TAG #URR8PPP .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0; up vote -3 down vote favorite Say, for example I have worked in the following companies, Company A => 2010 - 2011 Company B => 2011 - 2012 Company C => 2012 - Till Date Company D => Have offer Now assume Company D is asking to submit documents from my second last employer. So from the list of companies given, which company would be qualified as second last employer? software-industry employer share | improve this question asked Aug 10 '14 at 5:16 Rajaprabhu Aravindasamy 559 1 6 13 closed as off-topic by Jim G., jmort253 ♦ Aug 11 '14 at 1:58 This question appears to be off-topic. The users who voted to close gave this specific reason: "Questions seeking advice on company-specific regulations, agreements, or policies should be directed to your manager or HR department. Questions that address...
Read more

List of Gilmore Girls characters

Image
The season three cast—(Back row): Lane, Michel, Paris, Emily, Richard, Sookie, Miss Patty, Kirk; Front row: Jess, Luke, Lorelai, Rory, Dean This is a list of characters for the comedy-drama television series Gilmore Girls . Contents 1 Main characters 1.1 Lorelai Gilmore 1.2 Rory Gilmore 1.3 Sookie St. James 1.4 Lane Kim 1.5 Michel Gerard 1.6 Luke Danes 1.7 Emily Gilmore 1.8 Richard Gilmore 1.9 Paris Geller 1.10 Dean Forester 1.11 Jess Mariano 1.12 Kirk Gleason 1.13 Jason Stiles 1.14 Logan Huntzberger 2 Major recurring characters 2.1 Christopher Hayden 2.2 Jackson Belleville 2.3 Mrs. Kim 2.4 Tristin DuGray 2.5 Max Medina 2.6 Taylor Doose 2.7 Dave Rygalski 2.8 Marty 3 Recurring characters 3.1 Stars Hollow 3.2 Chilton 3.3 Yale 3.4 Other 4 Notable guest stars 5 Unseen characters 6 Notes 7 References Main characters Actor Character Appearances Season 1 Season 2 Season 3 Season 4 Season 5 Season 6 Season 7 A Year in the Life Lauren Graham Lorelai Gilmore...
Read more

Confectionery

Image
Prepared foods made with a lot of sugar or other cabohydrates "Sweetmeat" redirects here. For the racehorse, see Sweetmeat (horse). Not to be confused with Sweetbread. This Kransekake is a traditional Scandinavian baker's confection. Confectionery is the art of making confections , which are food items that are rich in sugar and carbohydrates. Exact definitions are difficult. [1] In general, though, confectionery is divided into two broad and somewhat overlapping categories, bakers' confections and sugar confections. [2] Bakers' confectionery, also called flour confections , includes principally sweet pastries, cakes, and similar baked goods. Sugar confectionery includes candies ( sweets in British English), candied nuts, chocolates, chewing gum, bubble gum, pastillage, and other confections that are made primarily of sugar. In some cases, chocolate confections (confections made of chocolate) are treated as a separate category, as are sugar-free versions of ...
Read more