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

---

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"

---

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.

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.

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.

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:

Thanx for reply,

@ 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.

Thanks for reply.

@ 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.

Quote:

---

Originally Posted by ypp174

Thanks for reply.

@ 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;
}

---

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.

Yep, it's OK for efficiency.

Code:

---


/*
 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;
}

---