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;
}