Find a powerset of a set in C

Question

The code below is an implementation of purely recursive solution to find a powerset of any given set. The input set is a string, and the output - array of strings. Both of them are wrapped into a structure for convenience. The underlying algorithm is pretty common one. The recursive function executes exactly 2^n - 1 times.

I've intentionally removed all memory allocation error checking to make the snippet shorter.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct set {
 char* data;
 int size;
} Set;
typedef struct pset {
 char **data;
 int size;
} PSet;
Set *initSet(char *str) {
 Set *set;
 set = malloc(sizeof(Set)); 
 set->data = calloc(strlen(str) + 1, 1); 
 strcpy(set->data, str);
 set->size = strlen(str);
 return set;
}
PSet *initPSet(const Set* sset) {
 // wrapper for recursive function getPSet
 void getPSet(PSet *pset, const Set *inputStr, int buffer, int index);
 PSet *pset = malloc(sizeof(PSet));
 
 pset->data = malloc (sizeof(char *) * (1 << sset->size));
 
 // empty set is a subset of any set
 pset->data[pset->size] = calloc(2, 1);
 strcpy(pset->data[pset->size], "");
 pset->size = 1;
 // in case the input set is empty return a set with just one element
 if (sset->size != 0)
 getPSet(pset, sset, 0, 0);
 return pset;
}
void getPSet(PSet *pset, const Set *set, int buffer, int index) {
 //allocating place for a new subset
 pset->data[pset->size] = calloc(strlen(pset->data[buffer]) + 2, sizeof(char));
 strcpy(pset->data[pset->size], pset->data[buffer]);
 pset->data[pset->size][strlen(pset->data[buffer])] = set->data[index];
 pset->size++;
 // local variable pos keeps track of a position of a prefix stored in pset for future recurrent calls
 int pos = pset->size - 1;
 index++;
 
 if (index >= set->size) return;
 getPSet(pset, set, buffer, index);
 getPSet(pset, set, pos, index);
}
int main () {
 Set *sset = initSet("abcd");
 PSet *pset;
 pset = initPSet(sset);
 for (int i = 0; i < pset->size; ++i) {
 printf("{%s}\n", pset->data[i]);
 }
 return 0;
}

• 1201ProgramAlarm: pset->size is used in initPSet without having been initialized.

Answer 1

Just a review of a small portion of code:

PSet *pset = malloc(sizeof(PSet));
pset->data = malloc (sizeof(char *) * (1 << sset->size));
pset->data[pset->size] = calloc(2, 1);

pset->size is not yet assigned a value. pset->data[pset->size] is a Bug. @1201ProgramAlarm

sizeof(char *) --> Is that the correct size? I need to look for the declarations of pset up some lines and then the definition of PSet some 20 lines upstream.

Consider below instead - no need to check if the correct type. The size is correct by inspection of this line alone.

pset->data = malloc(sizeof pset->data[0] * (1 << sset->size));

Later code uses int for indexing and buffer size, yet could have used unsigned and incur no additional cost in performance. To support unsigned, add u:

pset->data = malloc(sizeof pset->data[0] * (1u << sset->size));

---

Redundant string length calculation

Compiler may not optimize the 2 strlen() calls into 1. Recommend to do so by direct code.

//pset->data[pset->size] = calloc(strlen(pset->data[buffer]) + 2, sizeof(char));
//strcpy(pset->data[pset->size], pset->data[buffer]);
//pset->data[pset->size][strlen(pset->data[buffer])] = set->data[index];
size_t len = strlen(pset->data[buffer];
pset->data[pset->size] = calloc(len + 2, sizeof(char));
strcpy(pset->data[pset->size], pset->data[buffer]); // or memcpy()
pset->data[pset->size][len] = set->data[index]; // re-use `len`

---

Use const for unchanged refenced data

It better conveys code's intent, allows for some optimizations and greater functionally usage.

// Set *initSet(char *str) {
Set *initSet(const char *str) {

---

Missing freeing of memory

For general usage of these routines, de-allocation routines are needed like uninitSet() and uninitPSet().

• anfauglit: Appreciate your feedback. I especially like the idiom of dereferencing a pointer variable for the calculation of memory being allocated. The only thing that isn't that clear to me is using unsigned instead of int. Do you use it for better demonstration of your intentions or it yields some advantages in efficiency/allows for certain optimizations?
• chux: @anfauglit Increased range with u. 1u << sset->size good for sset->size in the range [0...N). 1 << sset->size good for sset->size in the range [0...N-1). Same efficiency. Other code would need to move from int indexing to support this wider range.