0
\$\begingroup\$

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;
}
\$\endgroup\$
1
  • 2
    \$\begingroup\$ pset->size is used in initPSet without having been initialized. \$\endgroup\$ Jan 11 '21 at 0:31
1
\$\begingroup\$

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().

\$\endgroup\$
2
  • \$\begingroup\$ 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? \$\endgroup\$
    – anfauglit
    Jan 14 '21 at 8:57
  • \$\begingroup\$ @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. \$\endgroup\$ Jan 14 '21 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.