Thread: possible combination of a string

Hi friends...

I need to write a program in C which will print all the combinations of a string with non-repeating characters. Example: “Say” will have the following: S, a,y, Sa, Sy, aS,Sy, yS, ya, aSy,Sya,ySa and so on. The string length is not known. The string will be a command line argument to the program.


The code that i have goes below but its not giving me the desired output. the output that i m getting from this program is like

#############OUTPUT##################
Enter the string : say

sya
ysa
yas
ays
asy
say
##################################

#############DESIRED OUTPUT##################
Enter the string : say

s
a
y
sa
sy
as
ys
ay
ya
sya
ysa
yas
ays
asy
say
###########################################

Code:

###########PROGRAM################
#include<stdio.h>
#include<string.h>
#include<alloc.h>
#include<conio.h>


void swap(char*,int);
void gotoloop(char*,int);

void main()
{
char *ch;
int i,j,k,l;
ch=(char*)malloc(20);
//clrscr();
printf("Enter the string\n");
gets(ch);

l=strlen(ch);
gotoloop(ch,l);

return;
}

void gotoloop(char *ch,int l)
{
int i,k;
k=l;

if(l<=1) 
return;


for(i=0;i<k;i++)
{
swap(ch,k);
l--;
gotoloop(ch,l);
l++;
if(k==2)
printf("\n%s ",ch);
}

}


void swap(char *ch,int r)

{
char c;
int i;

c=ch[r-1];
for(i=r-1;i>0;i--)
ch[i]=ch[i-1];
ch[0]=c;
}

This is not like a normal permutation of string.

Can anyone help me on this ASAP.

Thanks in advance

figure out how many of each length you have to process first
choose(m,n)
m! / (n!)(m-n)!
so for your example choose(3,1) is how many single char stirngs you need. 3! = 3x2x1 = 6
1! = 1, (3-1)! = 2
so 6/2 = 3 single chars

choose(3,2): 6/2 = 3 strings of length 2
choose(3,3): 1 string of length 3

now with that you have to get each string. from this example you will need to process 3 + 3 + 1 = 7 different strings. your current algorithm seems to be able to process the string right. You just need to process more than just "say" (1 of lenght 1) run it with "sa", "ay", "sy" (3 of length 2) and "a", "y", "s" (3 of length 1)