isPermutation method

Question

I wrote an isPermute method. Can I get some tips and advice on better coding style?

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

bool isPermute(char*, char*);
char* sort(char*);

int main(int argv, char **argc)
{
  printf("%s and %s are %spermutations of each other. \n", argc[1], argc[2], isPermute(argc[1], argc[2]) ? 
    "" : "not ");

  return 0;
}

bool isPermute(char* s1, char* s2)
{

  int size1 = strlen(s1);
  int size2 = strlen(s2);

  //default cases
  if((size1 != size2) || (size1 == 0) || (size2==0))
    return false;  

  if(strcmp(sort(s1), sort(s2)))
    return false;

  else
    return true;
}

char* sort(char* str1)
{
  int d=0, size = strlen(str1);
  char character;
  char *original = str1;

  char *result = (char *)malloc(size);

  for ( character = 'a' ; character <= 'z' ; character++ )
  {
     int i;
     for ( i = 0 ; i < size ; i++ )
     {
        if ( str1[i] == character )
        {
           result[d] = str1[i];
           d++;
        }
     }
     str1 = original;
  }
  return result;
}

Answer 1

First off:

bool isPermute(char*, char*);
char* sort(char*);

You could just move the function implementation over the main method, avoiding to have these declarations; however, that isn't really a big deal.

The convention for int main isn't:

int main(int argv, char **argc)

It normally is the opposite: argc is for the arg count and argv is for the arguments passed to the program.

So it really should be:

int main(int argc, char **argv)

Next:

printf("%s and %s are %spermutations of each other. \n", argc[1], argc[2], 
    isPermute(argc[1], argc[2]) ? "" : "not ");

You never checked if the program was actually passed two parameters, and so instead it should be (argc is the arg count from now on, and argv is the arguments)

if(argc == 3) 
{
    printf("%s and %s are %spermutations of each other. \n", argv[1], argv[2], 
        isPermute(argv[1], argv[2]) ? "" : "not ");
}
else 
{
    printf("Incorrect amount of parameters passed!\n");
    return -1;
}

The following:

if(strcmp(sort(s1), sort(s2)))
    return false;
else
    return true;

can be trimmed down to be just:

return !strcmp(sort(s1), sort(s2));

The following:

char *result = (char *)malloc(size);

You don't need to have the explicit cast (char *) as malloc returns a void*, so it can just be

char *result = malloc(size); 

Which doesn't detract from clarity in any real way.

Also, I've noticed that you are declaring variables for the for loops outside the loop, even though that isn't necessary (unless you are using C89, in which case, ignore this)

So this:

for ( character = 'a' ; character <= 'z' ; character++ )
{
     ...
}

would become

for (char character = 'a'; character <= 'z'; character++)
{
    ...
}

The same thing essentially applies for the other for loop.

for ( i = 0 ; i < size ; i++ )
{ 
    ...
}

would become

for (int i = 0; i < size; i++)
{
    ...
}

Answer 2

Corner case

This condition:

if((size1 != size2) || (size1 == 0) || (size2==0))
  return false;

Misses the case where both strings are empty, as the empty string is a permutation of the empty string.

Boolean return anti-pattern

  if(strcmp(sort(s1), sort(s2)))
    return false;

  else
    return true;

Becomes:

return ! strcmp(sort(s1), sort(s2))

It does the same, but it's shorter & simpler.

Answer 3

Memory issues

The following memory region is allocated but never freed and the size of allocated memory region is missing the terminating zero character.

     char *result = (char *)malloc(size);

The terminating zero charcter is not written to result but it is required for the result string but is required for the strcmp() function to work correctly.

Algorithm

It works only on lower case characters. It produces wrong results when other characters are used. This should be either mentioned in the documentation (if intended), maybe checked at runtime or corrected.

Extending the algorithm to all characters except zero increases the runtime due to the nested loops from O(size * 26) to O(size * 255) which might be undesired for small strings. Have a look at https://stackoverflow.com/questions/33294426/sort-string-by-character-in-c-programming for a character sorting using quicksort.

Documentation

The sort() and isPermute() functions are missing entire documentation about what they do, the parameter and its return values. Something like

    /** sort() takes a zero terminated character string and returns a
    string of the same size with contents sorted lexicographically.
    The returned string has to be deallocated by the caller using free(). */

Answer 4

these two lines cause the compiler to output warnings about conversion to different types because strlen() returns a size_t, not a int

  int size1 = strlen(s1);
  int size2 = strlen(s2);

suggest using:

  size_t size1 = strlen(s1);
  size_t size2 = strlen(s2);

for readability, follow the axiom: only one statement per line and (at most) one variable declaration per statement

SO this line:

int d=0, size = strlen(str1);

becomes:

int d=0;
size_t size = strlen(str1); // remember strlen() returns a 'size_t` not an 'int'

after applying the above changes, then these lines:

int i;
for ( i = 0 ; i < size ; i++ )

become

 for ( size_t i = 0 ; i < size ; i++ )

Always check the first parameter to main() to assure that the command line had the correct number of parameters before accessing anything beyond (in your case) argc[0] And when the command line did not contain the correct number of parameters, the output, on stderr, via fprintf(stderr, ...) how the program should be invoked

Note: by convention, the main signature is written like this:

int main( int argc, char *argv[] )

where argc is the COUNT of number of command line parameters

where argv[] is a VECTOR of pointers to character strings of the parameters

Answer 5

This is not about a coding style but rather about an efficient algorithm: instead of sorting characters in strings you might just count them.

Prepare an array of integers, indexed with characters. Fill it with zeros. Scan a string, incrementing a counter for each character found. Then scan the other string, but this time decrement counters.

The two strings are anagrams (permutations) of each other iff all the counters are zero.