# See I have 2 string, i need to check whether 2nd sting is jumbled form of first sting

• 09-21-2012
ypp174
See I have 2 string, i need to check whether 2nd sting is jumbled form of first sting
Output is coming equal; how come?

If string 1 is "dabcd" and string 2 is "bcadd" then it should show similar strings.
Any one can suggest any other easy way to do this....

Code:

```#include<stdio.h>   int main() {     char a[]="abcd";     char b[]="zdab";     char temp = '0';     int i=0,j=0;     int n=sizeof(a);      for(i=0;i<n-1;i++)     {        for(j=0;j<n-i-1;j++)       {          if(a[j]>a[j+1])         {              temp =a[j];             a[j] = a[j+1];             a[j+1]=temp;         }            if(b[j]>b[j+1])         {              temp =b[j];             b[j] = b[j+1];             b[j+1]=temp;         }        }      }          for(i=0;i<n;i++)     {        printf("%c %c\n",a[i],b[i]);     }    if(strcmp(a,b)==0)       printf("similar and jumbled");   else       printf("unequal");        return 0; }   output :   a a b b c d d z similar and jumbled```
• 09-21-2012
Salem
Somehow, your "sort" function managed to move the \0 to the start of the string.

Code:

```Breakpoint 1, main () at foo.c:33 33          if(strcmp(a,b)==0) (gdb) print a \$1 = "\000abcd" (gdb) print b \$2 = "\000abdz"```
• 09-21-2012
christop
What is the output when you change this line:
Code:

`      printf("%c %c\n",a[i],b[i]);`
to this?
Code:

`      printf("%d %d\n",a[i],b[i]);`
Hint: your sorting loop needs to be fixed.
• 09-21-2012
ypp174
suggest easier way plzzz
Quote:

Originally Posted by christop
What is the output when you change this line:
Code:

`      printf("%c %c\n",a[i],b[i]);`
to this?
Code:

`      printf("%d %d\n",a[i],b[i]);`
Hint: your sorting loop needs to be fixed.

Yup...
if i use n = sizeof(a)-1;

then its working....:)

Any 1 plz suggest easier way to do this.
• 09-21-2012
Salem
Well how are you measuring "similar"?

At the moment, you're comparing "abcd" with "abdz". The comparison stops being equal at 50% of the string length.

But rearranged as "abdc" and "abdz", the comparison stops being equal at 75% of the string length.

Perhaps a different approach would be to take
char a[]="abcd";
char b[]="zdab";

and eliminate from both arrays any letter which is common to both.

So for example, on the first pass, you see both have an 'a', so both become
a[]="bcd";
b[]="zdb";

Eventually, you end up with
a[]="c";
b[]="z";
where each array contains only letters not in the other string.

Obviously, if the strings were identical, or just a permutation, both resultant strings would be empty.

How you decide how two non-empty strings are on a scale from "very similar" to "different" is another matter.
• 09-21-2012
Use "counting sort" to record the letters into another array. csorta[128] would have csorta[ascii value of a letter]++ (incremented). So 'a' would give csorta['a']++.

if b[] had an 'a' in it, then it would also have csortb['a']++. Adding 1 to csortb['a'] for every 'a' in the b string of chars.

Then just check csorta to csortb

Pseudo of code:
Code:

``` for(i='A',notEqual=0;i<='z'; i++) {   if(csorta[i] != csortb[i]) {     notEqual = 1;     break;   } } if(notEqual)   printf("Strings are not equal\n"); else   printf("Strings have the same letters in them\n");```
You can download an ascii table from several places on the net, just google it. Any programming book, and lots of compilers have them, as well. You can also make your own compiler show them, pretty easily (not as convenient though unless you print it out).

The advantage is shorter code, and no sorting. No char's are moved in the running of this program! :cool:
• 09-23-2012
ypp174

@ Salem : I understood, means I am first sorting n elements and then comparing n elements.
But according to your logic i need to delete common k element and compare remaining only n-k elements.
• 09-23-2012
ypp174

@ Adak : I thought of this solution but user input any character even spacial character.
So if input string length is more than available total ascii values(255) then it is ok
but what if input string length is small like 10 to 20 letter then it would be not efficient i guess.
here also first we are sorting n element into an array then comparing until we find mismatch, so more comparison happening.
• 09-23-2012
Quote:

Originally Posted by ypp174

@ Adak : I thought of this solution but user input any character even spacial character.
So if input string length is more than available total ascii values(255) then it is ok
but what if input string length is small like 10 to 20 letter then it would be not efficient i guess.
here also first we are sorting n element into an array then comparing until we find mismatch, so more comparison happening.

That's a very thoughtful reply. I'm impressed by it.

Take a run at this, however, and tell me what you think.

Code:

```#include <stdio.h> #include <string.h> int encrypt (int num); int main(void) {   char a[50]={"Once a jolly swagman"};   char b[50]={"cegajlnwolsanOyam"};   char counta[127], countb[127];   int i, lena, lenb, maxlen, notEqual;   for(i=0;i<127;i++) {       counta[i]=0;       countb[i]=0;   }     lena=strlen(a);                    //get their respective lengths   lenb = strlen(b);   if(lena > lenb)       maxlen = lena;   else       maxlen = lenb;         for(i=0;i<=maxlen;i++) {            //and catalogue the values       if(i<lena)         counta[a[i]]++;         if(i<lenb)         countb[b[i]]++;   }   for(i='A',notEqual=0;i<='z';i++) { //now compare them       if(counta[i] != countb[i]) {         notEqual = 1;         printf("Not equal: %c  counta[i]: %d  countb[i]: %d\n",i,counta[i], countb[i]); getchar();         break;       }       //printf("i: %c Is equal: counta[i]: %d  countb[i]: %d\n",i,counta[i], countb[i]); getchar();   }   if(notEqual)       printf("Strings contain different letters\n");   else       printf("Strings contain the same letters\n");   return 0; }```
• 09-23-2012
laserlight
Quote:

Originally Posted by ypp174
I thought of this solution but user input any character even spacial character.
So if input string length is more than available total ascii values(255) then it is ok
but what if input string length is small like 10 to 20 letter then it would be not efficient i guess.

You still are going to assume that each character fits into a char, so this means 256 different values, assuming that CHAR_BIT is 8. Therefore, counting sort is applicable.

As for efficiency: if the input string length is small and limited to only a few values, then indeed Adak's idea for using counting sort would not be efficient. On the other hand, efficiency does not matter when the size of the input is so small. On a modern computer, I expect that even bogosort would be fast enough to sort a 20 character array before you can say "the array is sorted!"

Quote:

Originally Posted by ypp174
here also first we are sorting n element into an array then comparing until we find mismatch, so more comparison happening.

With an efficient sort, you will likely use fewer comparisons than without sorting, assuming that the size of the input is large enough.
• 09-23-2012
``` /*  Words are from the Roberta Flack version of the song, 1969, from here: http://www.youtube.com/watch?v=hOFrGbuUqnQ Great listen! ;) */ #include <stdio.h> #include <string.h> #include <time.h> int encrypt (int num); int main(void) {   char a[]={       "The first time, ever I saw your face.\n"       "I thought the sun, rose in your eyes.\n"       "And the moon and the stars, were the gifts you gave,\n"       "to the dark, and the endless skies, my love.\n"       "To the dark, and the endless skies.\n\n"       "And the first time, ever I kissed your mouth.\n"       "I felt the earth, move in my hand.\n"       "Like the trembling heart, of a captive bird,\n"       "that was there, at my command, my love.\n"       "That was there, at my command, my love.\n\n"       "And the first time, ever I lay with you,\n"       "I felt your heart, so close to mine.\n"       "And I knew our joy, would fill the earth,\n"       "and last, till the end of time, my love.\n"       "And it would last, till the end of time, my love.\n\n"       "The first time, ever I saw, your face.\n"       "Your face. Your face. Your face.\n"   };   char b[]={       "The first time, ever I saw your face.\n"       "I thought the sun, rose in your eyes.\n"       "And the moon and the stars, were the gifts you gave,\n"       "to the dark, and the endless skies, my love.\n"       "To the dark, and the endless skies.\n\n"       "And the first time, ever I kissed your mouth.\n"       "I felt the earth, move in my hand.\n"       "Likes the trembling heart, of a captive bird,\n"      //appended an s to Like,       "that was there, at my command, my love.\n"       "That was there, at my command, my love.\n\n"       "And the first time, ever I lay with you,\n"       "I felt your heart, so close to mine.\n"       "And I knew our joy, would fill the earth,\n"       "and last, till the end of time, my love.\n"       "And it would last, till the end of time, my love.\n\n"       "The first time, ever I saw, your face.\n"       "Your face. Your face. Your face.\n"   };         char counta[127], countb[127];   int i, lena, lenb, maxlen, notEqual;   clock_t start,stop;   start=clock();   for(i=0;i<127;i++) {       counta[i]=0;       countb[i]=0;   }     lena=strlen(a);                    //get their respective lengths   lenb = strlen(b);   if(lena > lenb)       maxlen = lena;   else       maxlen = lenb;         for(i=0;i<=maxlen;i++) {            //and catalogue the values       if(i<lena)         counta[a[i]]++;         if(i<lenb)         countb[b[i]]++;   }   for(i='A',notEqual=0;i<='z';i++) { //now compare them       if(counta[i] != countb[i]) {         notEqual = 1;         printf("Not equal: %c  counta[i]: %d  countb[i]: %d\n",i,counta[i], countb[i]); //getchar();         break;       }       //printf("i: %c Is equal: counta[i]: %d  countb[i]: %d\n",i,counta[i], countb[i]); getchar();   }   if(notEqual)       printf("Strings contain different letters\n\n");   else       printf("Strings contain the same letters\n");   stop = clock();   printf("Elapsed time: %f seconds\n",(double)(stop-start)/CLOCKS_PER_SEC);   printf("Display the strings [y/any] ? ");   i=getchar();   if(i=='y')       printf("a:\n%s\n\n b:\n%s\n",a,b);   return 0; }```