C program to generate all possible combinations of a n letters word

#include"stdio.h"
#include"conio.h"
#include"string.h"

int flag=0,hold,n;
char str[100],str2[100];
unsigned long fact(unsigned long f) /*for getting factorial*/
{
return f==0?1 : f*fact(f-1);
}

void swap(char *s) /*to swap s[n-2] and s[n-1]*/
{
char temp=s[n-1];
s[n-1]=s[n-2];
s[n-2]=temp;
}
void display(char *s) /*to display string s*/
{
int i=0;
static int j=1;
printf("%d)",j++);
for (i=0;i<=n;i++)
printf("%c ",s[i]);
printf("\n");

}
void shift(char *st,int hol) /*to shift the characters
leftwise from st[n-1]
to st[1]*/
{
int i,temp;
if(hol==fact(n-1)/2)
flag=1;
temp=st[1];
for(i=1;i st[i]=st[i+1];
st[n-1]=temp;
}
void touch(char *s) /*to shift the original
string leftwise from
(n-1)th to 1st position
everytime the function
is called*/
{
int i,temp=s[0];
for(i=0;i<=n-1;i++)
s[i]=s[i+1];
s[n-1]=temp;
}
void main()
{
int i,j;
clrscr();
printf("\nPlease enter the word: ");
gets(str);
n=strlen(str);
strcpy(str2,str);
puts(str2);
for(i=1;i<=n;i++)
{
flag=0;
strcpy(str,str2); /*at initial call i.e str=str2
but for later stage the
value of str gets replenished
by value of str2*/
hold=1; /*variable to control value of flag from
function shift()*/
while(flag==0)
{
display(str);
swap(str);
display(str);
strcpy(str,str2); /*str2 has been copied in str
so that leftwise shift can
be done from (n-1)th to 1st
position*/
shift(str,hold++);
}
touch(str2);
}
getch();
}



/*LOGIC-The logic of the program is to keep the original
string and its copy.We display the content.

1)Now we shift the character in the (n-1)th and the
(n-2)th position in the main function.Again we display
the content of the string.Let us take example - abcd.
Here its
a b c d
a b d c

2)Now we shift from (n-1)th position to 1st position in
left wise manner(but not upto 0th position).We do it
and repeat step 1) again and again at each left shift of
step 2, till we find all the combinations from 1st to
(n-1)th position.
[Actually this logic simply finds all the combination in
binary logic at O(n) (i.e O(n-1)+O((n-1)/2))]
so we get
a c d b
a c b d
a d b c
a d c b

3)Now we just do the process again but now we shift leftwise
from (n-1)th to 0th position until all the characters in the
string have been scanned.(This is done with the help of the
copy of the original string,mentioned earlier in step 1).We
repeat step 2) again and again at each left shift of step 3,
till we find all the combinations of the 'n letters word'.
[Here in this step the actual complexity of the program
could be found as O(n^2) (i.e O(n*n) here left n is of step 3
and right n is from step 2).
Hence the complexity is O(n^2)].
*/

-RAJA GHOSH,16TH JULY,2010