#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$
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$
If you find time , pls told about Basic things of Android Development.
ReplyDeleteThanks in Advance..
Best Regards,
Senthilvelan S :-)