Print all subsets and permutations of a string

Question

The following code is designed to accept a string from the user that is at most 5 characters long. It will then find each possible substring of the string and print all possible permutations of each substring.

This is the first time I've done my utmost to prevent memory leaks by freeing every malloc. Even Valgrind seems to be happy, but I'm wondering if anyone here will be able to spot any bad practices, especially regarding memory allocation.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
char * createString();
void genSubsets(char *);
char * genBetween(char *, int, int);
void swap(char *, char *);
void permute(char *, int, int);
int alreadyPermuted(char *);
char ** permutations;
unsigned int numPermuted = 0;

int main()
{
    permutations = malloc(sizeof(char*) * 120); 
    memset(permutations, '\0', 120);
    int index = 0;
    for(index = 0; index < 120; index++)
    {
        permutations[index] = malloc(sizeof(char) * 6);
        memset(permutations[index], '\0', 6);
    }
    // 120 is 5!
    //So this will be the maximum space needed
    char * string  = createString();
    scanf("%5[^\n]s", string);
//  printf("%s\n", string);
    genSubsets(string);
    free(string);   

    for(index = 0; index < 120; index++)
    {
        free(permutations[index]);
    }
    free(permutations);
    return 0;
}
char * createString()
{
    char * string = malloc(sizeof(char) * 6);
    if(string)
    {
        memset(string,'\0',6);
        return string;
    }
    else
    {
        puts("Malloc failed!");
        abort();
    }
}
void genSubsets(char * string)
{
    int counter1;
    int counter2;
    int size = strlen(string);
    //permute(string, 0, size);
    for(counter1 = 0; counter1 < size; counter1++)
    {
        for(counter2 = counter1; counter2 < size; counter2++)
        {
            char * generatedSubString = genBetween(string, counter1, counter2);
            if(generatedSubString[0] != '\0' && numPermuted < 120)
            {
        //      printf("Substring : %s\n", generatedSubString);
                permute(generatedSubString, 0 , strlen(generatedSubString));
            }
            free(generatedSubString);       
        }
    }
}
char * genBetween(char * string, int begin, int end)
{
    char * subString = createString();
    int counter;    
    if(!subString)
    {
        puts("Realloc failed.");
        abort();
    }
    for(counter = begin; counter <= end; counter++)
    {
        subString[counter-begin] = string[counter]; 
    }
    //free(string);
    return subString;
}
void swap(char * first, char * second)
{
    char temp = *first;
    *first = *second;
    *second = temp;
}
void permute(char * string, int begin, int end)
{
    int count = 0;
    if(begin == end && strlen(string) > 0 && !alreadyPermuted(string) && numPermuted < 120)
    {
        printf("%s\n", string);
        strcpy(permutations[numPermuted], string);
        numPermuted++;
        return;
    }
    for(count = begin; count <= end; count++)
    {
        swap(string+begin, string+count);
        permute(string, begin+1, end);
        swap(string+begin, string+count);
    }

}
int alreadyPermuted(char * string)
{
    int count = 0;
    for(count = 0;numPermuted < 120 &&  count <= numPermuted; count++)
    {
        if(strcmp(permutations[count], string)==0)
        {
            return 1;
        }   
    } 
    return 0;
}

Answer 1

• Some (most of?) dynamic allocations seem unnecessary. A call to createString can be safely replaced with a local char string[6]; Similarly, a call to genBetween could be reduced essentially to

  char generatedSubString[6];
  strncpy(generatedSubString, string + counter1, counter2 - counter1);
  

• Testing for numPermuted < 120 looks strange. You should trust your math. If you do not, don't fail the test silently, but rather assert(numPermuted < 120), and if it triggers, revisit your assumptions.

• A search for already permuted (in fact, already visited) substring is suboptimal. Consider filling the permuted array in sorted order (to enable binary searching it).