A simple program to calculate combinations of a string using recursion, I have used a malloc string of size 100 , you can change it to whatever value you want. The author is currently working at Microsoft.
for eg if input string is abcd and you want all 3 letter combinations, the o/p would be
abc
abd
acd
bcd
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void Combinations(char string[],int stack[],int combLength,int leftIndex);
void ComputeCombinations(char string[]);
void DisplayStack(int stack[],int stringLength,char string[]);
int main()
{
char *string;
printf("\nEnter the string ..\n");
string = (char *)malloc(100 * sizeof(char));
if(!string)
{
printf("\nmemory allocation for string failed exiting ..\n");
exit(1);
}
gets(string);
ComputeCombinations(string);
return 0;
}
void ComputeCombinations(char string[])
{
int stringLength = 0;
int *stack;
int index = 0;
int combLength = 0;
int combIndex = 0;
stringLength = (int)strlen(string);
stack = (int *)calloc(stringLength,sizeof(int));
if(!stack)
{
printf("\nmemory allocation for stack failed exiting ..\n\n");
exit(1);
}
for(combIndex = 1;combIndex <= stringLength;combIndex++)
{
printf("\n %d letter combinations ...\n\n",combIndex);
for(index = 0; index < stringLength;index++)
{
stack[0] = index;
Combinations(string,stack,combIndex,index);
}
}
return;
}
void Combinations(char string[],int stack[],int combLength,int leftIndex)
{
static int stringLength = (int)strlen(string);
static int riteIndex = stringLength;
static int level = 0;
//Initialiaze the left index
if(level == 0)
{
leftIndex = stack[0]+1;
}
//if the current depth of tree = combinations length then print & return
if(level == combLength - 1)
{
DisplayStack(stack,combLength,string);
return;
}
level++;
//recurse from current index to end of string
for(;leftIndex < riteIndex;)
{
stack[level] = leftIndex;
leftIndex++;
Combinations(string,stack,combLength,leftIndex);
}
level--;
}
void DisplayStack(int stack[],int stringLength,char string[])
{
int index = 0;
for(index = 0; index < stringLength;index++)
{
printf(" %c ",string[stack[index]]);
}
printf("\n");
}
Some constructive comments:
1. exit (0) means successful return from a function. In case of unsuccessful memory allocation use, exit (1) instead of exit (0)
2. Always send the errors to the error stream rather than the output stream. In most of the cases the error stream is the ouput stream ie your monitor, but in specific cases it can be a log file.
3. A lightweight way to add a newline rather than writing printf ("\n") ; is putchar ('\n') ; 4. According to the principles of Software Engineering, the less the parameters passed to the functions, the better the function is. If your passed parameters exceed 4, try to re analyze your design.
The number of parameters passed is directly proportional to the complexity of the function.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.