Monday, October 18, 2010

Find the permutation and combination for a given string

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

#define ERRNUM -1
#define SUCCESS 0

#define TRUE 1
#define FALSE 0

#define TOTAL_ALPHA 26

/* Function   : permutations
 * Args       : str [IN]
 *              index [IN]
 *              result [IN/OUT]
 * Description: Function will print all the permutations and combinations of a given string 
 *              without repeated patterns. PnC(ABC) = { A+PnC(BC), B+PnC(CA), C+PnC(AB) } 
 * Note       : This "without repeated patterns" will not work for non-alpha characters [TBD]. 
 */
int permutations (char *str, int index, char *result)
{
  char *temp = NULL;           // To store the given string for processing
  int len = strlen (str);      // Length of the given string
  int count = 0;               // Counter variable used in the loop
  int j = 0;                   // Temporary variable
  char found[52] = {0};        // To check the variable to check the duplicate characters to avoid duplicate patterns

  /* Allocate memory for the temp variable to store the given string for processing.
   * So that the given string will not change. 
   */
  temp = (char *) calloc (len+1, sizeof (char));
  if (NULL == temp)
  {
    fprintf (stderr, "Memory allocation failed.\n");
    return ERRNUM;
  }

  /* Copy the given string into the temporary variable */
  strcpy (temp, str);

  /* Traverse through the string and find the permutations and combinations of the substring 
   * PnC(ABC) = { A+PnC(BC), B+PnC(CA), C+PnC(AB) } 
   */
  for (count=0; count < len; count++)
  {
    char ch = 0;
    
    *(result + index) = *temp;
    if (1 == len)
    {
      /* We can store in an array of string or a stack */
      printf ("%s\n", result);
    }
    else
    {
      if (isupper (*temp))
      {
        
        if (FALSE == found [TOTAL_ALPHA + (*temp) - 'A'])
        {
          found [TOTAL_ALPHA + (*temp) - 'A'] = TRUE;
        }
        else
        {
          /* Its a duplicate character */
          goto NEXT;
        }
      }
      else if (islower (*temp))
      {
        if (FALSE == found [(*temp) - 'a'])
        {
          found [(*temp) - 'a'] = TRUE;
        }
        else
        {
          /* Its a duplicate character */
          goto NEXT;
        }
      }
      
      /* We can store in an array of string or a stack */
      for (j=0; j<=index; j++)
      {
        printf ("%c", *(result+j));
      }
      printf ("\n");

      /* Find the permutations and combinations for the substring too */
      if (ERRNUM == permutations (temp+1, index+1, result))
      {
        return ERRNUM;
      }

    NEXT:
      ch = *temp;
      memcpy (temp, temp+1, len-1);
      temp[len-1] = ch;
    }
  }

  /* Free the allocated memory for the temporary variable */
  free (temp);

  return SUCCESS;
}

int main (int argc, char *argv[])
{
  char *result = NULL;        // Variable to store the result for printing 
  int retVal = SUCCESS;       // Variable to stroe the return value

  // No code to check/validate the input [TBD].

  if (NULL == result)
  {
    result = (char *) calloc (strlen (argv[1])+1, sizeof (char));
    if (NULL == result)
    {
      fprintf (stderr, "Memory allocation failed.\n");
      return ERRNUM;
    }
  }

  retVal = permutations (argv[1], 0, result);
  
  free (result);
    
  return retVal;
}
The results:
prompt$ ./permutationsNconbination ABC

A

AB

ABC

AC

ACB

B

BC

BCA

BA

BAC

C

CA

CAB

CB

CBA

prompt$ ./permutationsNconbination AAB

A

AA

AAB

AB

ABA

B

BA

BAA

prompt$ ./permutationsNconbination AAA

A

AA

AAA

prompt$