Hey I was having a problem with a homework problem in my algorithms class. I have to create all the permutations for the input, using C. You can assume that you will only use letters a-z and there will be no duplicates.
I have tried to do this for several hours and still cannot figure it out. I have written it out on paper and it looks fine, I just can't see what's going wrong. I was hoping someone could look at it, and see if they could figure out the logic error.
My sample input was: abc
My code calls permutate(abc, 0, 3)
My output:
abc
bb
aac
aa
aba
bb
voidpermutate(charstring[],intn,intsize){inti;inttemp;if(n>=size){return;}else{for(i=n;i<size;i++){///////////Puts the character in the front///////////////temp=string[i];string[i]=string[n];string[n]=temp;/////////////////////////////////////////////////////////printf("%c",string[i]);permutate(string,n+1,size);//////////////////Puts the character back in its spot so it can be done again//////////temp=string[i];string[i]=string[n];string[n]=temp;///////////////////////////////////////////////////////////////////////////////////////}printf("\n");}}
I think there is a more elegant solution to this...
The basic idea is that you just pass over the string and concatenate every char in the string with another call of the function which in turn will receive the original string Without that character. At length == 1 you just return the string.
void_permutate(charalphabet[],intn,intpos){if(pos<n){for(inti=pos;i<n;++i){// swap charsinttmp=alphabet[pos];alphabet[pos]=alphabet[i];alphabet[i]=tmp;// do recursion magic_permutate(alphabet,n,pos+1);// swap chars back into original orderalphabet[i]=alphabet[pos];alphabet[pos]=tmp;}}else{printf(alphabet);printf("\n");}}voidpermutate(charalphabet[]){// we need to allocate new memory, since constant parameters will cause segfaultschar*tmp=newchar[strlen(alphabet)+1];strcpy(tmp,alphabet);// this is where all the magic happens_permutate(tmp,strlen(tmp),0);// remember to clean updelete[]tmp;}
C+ +, but it shouldnt detract from the algorithm too much.
say you have and alphabet string of "123".
You pick each individual char and swap it into the first position. Now you pick each of the remaining chars and swap it into the second position. Rinse and repeat until theres only one position left.
Hey I was having a problem with a homework problem in my algorithms class. I have to create all the permutations for the input, using C. You can assume that you will only use letters a-z and there will be no duplicates.
I have tried to do this for several hours and still cannot figure it out. I have written it out on paper and it looks fine, I just can't see what's going wrong. I was hoping someone could look at it, and see if they could figure out the logic error.
My sample input was: abc My code calls permutate(abc, 0, 3)
My output: abc bb
aac aa
aba bb
I think there is a more elegant solution to this...
The basic idea is that you just pass over the string and concatenate every char in the string with another call of the function which in turn will receive the original string Without that character. At length == 1 you just return the string.
Shouldnt be much longer than 2-3 lines. :-P
Could you post an example, of what you mean?
C+ +, but it shouldnt detract from the algorithm too much.
say you have and alphabet string of "123".
You pick each individual char and swap it into the first position. Now you pick each of the remaining chars and swap it into the second position. Rinse and repeat until theres only one position left.
Edit: WikiCreole seems broken.