#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 :-)