195 - Anagram

[Stefan Pochmann]

Maybe you're just too restrictive on the length of the string? Try 5000 instead of 50.

[C8H10N4O2]

767668 2002/03/02 13:12:08.862 Accepted 0:00.950 428 James Mao ... C++ 195 - Anagram

Finally. Thank you so much for all your advice. I guess I was just overlooking the small details.

[taj79]

Judge says:

Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

Before crash, it ran during 0.000 seconds.

Why is it not working?Is it because judge is using string of bigger size? on my comp the prog can work for maxim 6 chars.
Should i improve that? But how ?
i can't increase MAX1 anymore.

C

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string.h>

#define MAX 50
#define MAX1 30000

int fact(int n);
void func(char s[],int t);
void comb(int n,char C[],char S[][MAX]);
void quicksort(char A[],int p,int r);
int partition(char A[],int p,int r);

main()
{ int i,n,t;
char s[MAX];

gets(s);
n = atoi(s);
/* printf("\n %d",n); */
for(i=0;i<n;i++)
{ gets(s);/* printf("\n %s",s); */
t=-1;
do{
if(s[++t] == '\0')
{ --t;
break;
}
}while(s[t] != '\0');
/* printf("\n %s",s);
printf("\n i = %d t= %d",i,t); */
if(i != 0)
printf("\n");
func(s,t);
}
printf("\n");
}

int fact(int n)
{
if(n==0)
return(1);
if(n == 2 || n== 1)
return(n);
else
return(n*fact(n-1) );
}

void func(char s[],int t)/* t = num of char - 1 */
{char S[MAX1][MAX];
int i,j,repeat =0,u,check;

/* printf("\n Inside func() s= %s\n",s);
for(i=0;i<=t;i++)
printf(" %c",s); */

quicksort(s,0,t);
/* printf("\n After quick sort: \n");
for(i=0;i<=t;i++)
printf(" %c",s); */
for(i=0;i<t;i++)
if(s == s[i+1])
repeat = 1;
/* printf("\nrepeat = %d\n",repeat); */

comb(t+1,s,S);
/* printf("\n Inside func() After comb() s= %s\n",s); */
if(repeat == 0)
{
for(i=0;i< fact(t+1) ;i++)
{if(i != 0)
printf("\n");
for(j=0;j<= t;j++)
printf("%c",S[j]);
}
}
else
{
for(i=0;i< fact(t+1) ;i++)
{ if(i==0)
printf("%s",S);

else{check = 0;
for(u=i-1;u>=0;u--)
if( strcmp(S,S) == 0 )
{ check=1;
break;
}
if(check == 0)
printf("\n%s",S);

}
}
}

return;
}


void quicksort(char A[],int p,int r)
{int q,count=0;
/* printf("\n\n Entered quicksort\n\n");
printf("p = %d r = %d\n",p,r); */
if(p<r){ ++count;
/* printf("%d",count); */
q = partition(A,p,r);
quicksort(A,p,q);
quicksort(A,q+1,r);
}
return;
}

int partition(char A[],int p,int r)
{ char x,u;
int i,j;
x = A[p];
i = p-1;
j = r+1;
while(1){
do{--j;
}while(A[j]>x);
do{ ++i;
}while(A<x);
if(i < j)
{ u = A ;
A= A[j];
A[j] = u;
}
else
return(j);
}
}

void comb(int n,char C[],char S[][MAX])
{ int i,j,t,u,e;
static int count =0;
char C1[MAX],S1[MAX1][MAX];
/* printf("\n Inside comb n = %d",n); */
if(n==2)
{
S[0][0] = C[0];
S[0][1] = C[1];
S[1][0] = C[1];
S[1][1] = C[0];
return;
}
if(n > 2)
{
for(i=0;i<n;i++)/* #a */
{
t= -1;
for(j=0;j<n;j++)
if(j != i)
C1[++t] = C[j];
/* printf("\ncount = %d t= %d Elements of C1 are: ",count,t);
for(j=0;j<=t;j++)
printf(" %c",C1[j] ); */
comb(n-1,C1,S1);
/* printf("\ncount = %d Inside comb itself n-1 = %d",++count,n-1);
for(e=0;e< fact(n-1) ;e++)
{ printf("\n");
for(j=0;j< n-1;j++)
printf("%c",S1[e][j]);
} */
for(j= i*fact(n-1) ;j< (i+1)*fact(n-1) ;j++)
{ S[j][0] = C[i];
for(u=0;u<n-1;u++)
S[j][u+1]= S1[j - i*fact(n-1)];
}
}/* END of for #a */
return;
}
}[c][/c][c][/c][c][/c]

[cyfra]

Hi!

When I compiled and your you program on my computer it has a SIGSEGV during reading -- during first while....

So this the place you should check ..

BTW. Is working on your computer ??

Good Luck

PS.
On the next time PLEASE use bbtags for program codes...

[Ivor]

If I remeber correctly then the length of the line should be bigger than 50. Set MAX to 100 -- it should help.

Ivor

[taj79]

Now my prog is like this:

Code: Select all

[c]

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX 20
#define MAX1 50000

int fact(int n);
void func(char s[],int t);
void comb(int n,char C[],char S[][MAX]);
void quicksort(char A[],int p,int r);
int  partition(char A[],int p,int r);

main()
{ int i,n,t;
  char s[MAX];

 gets(s);
 n = atoi(s);
/*  printf("\n %d",n);  */
 for(i=0;i<n;i++)
  { gets(s);/* printf("\n %s",s); */
    t=-1;
    do{
       if(s[++t] == '\0')
       { --t;
        break;
       }
      }while(s[t] != '\0');
   /*   printf("\n %s",s);
      printf("\n i = %d    t= %d",i,t);  */
      if(i != 0)
       printf("\n");
    func(s,t);
  }
  printf("\n");
}

int fact(int n)
{
  if(n==0)
   return(1);
  if(n == 2 || n== 1)
    return(n);
    else
     return(n*fact(n-1) );
}

void func(char s[],int t)/* t = num of char - 1   */
{char S[MAX1][MAX];
  int i,j,repeat =0,u,check;

/*  printf("\n Inside func()  s= %s\n",s);
  for(i=0;i<=t;i++)
    printf(" %c",s[i]);  */

  quicksort(s,0,t);
/*  printf("\n After quick sort: \n");
 for(i=0;i<=t;i++)
    printf(" %c",s[i]);  */
 for(i=0;i<t;i++)
   if(s[i] == s[i+1])
     repeat = 1;
/*  printf("\nrepeat = %d\n",repeat);  */

  comb(t+1,s,S);
/*  printf("\n Inside func()  After comb()  s= %s\n",s);  */
  if(repeat == 0)
  {
  for(i=0;i< fact(t+1) ;i++)
      {if(i != 0)
        printf("\n");
        for(j=0;j<= t;j++)
        printf("%c",S[i][j]);
      }
  }
  else
  {
   for(i=0;i< fact(t+1) ;i++)
   { if(i==0)
     printf("%s",S[i]);

     else{check = 0;
          for(u=i-1;u>=0;u--)
           if( strcmp(S[u],S[i]) == 0  )
	     { check=1;
	       break;
	     }
	   if(check == 0)
          printf("\n%s",S[i]);

	  }
   }
  }

  return;
}


void quicksort(char A[],int p,int r)
  {int q,count=0;
/*   printf("\n\n Entered quicksort\n\n");
   printf("p = %d    r = %d\n",p,r);  */
   if(p<r){    ++count;
/*       printf("%d",count);  */
       q = partition(A,p,r);
       quicksort(A,p,q);
       quicksort(A,q+1,r);
       }
       return;
   }

   int  partition(char A[],int p,int r)
   { char x,u;
     int i,j;
     x = A[p];
     i = p-1;
     j = r+1;
     while(1){
            do{--j;
	      }while(A[j]>x);
	    do{ ++i;
	      }while(A[i]<x);
	    if(i < j)
	    { u = A[i] ;
	      A[i]= A[j];
	      A[j] = u;
	    }
	    else
	     return(j);
	     }
   }

void comb(int n,char C[],char S[][MAX])
{ int i,j,t,u,e;
  static int count =0;
  char C1[MAX],S1[MAX1][MAX];
/*  printf("\n Inside comb n = %d",n);  */
  if(n==2)
   {
    S[0][0] = C[0];
    S[0][1] = C[1];
    S[1][0] = C[1];
    S[1][1] = C[0];
    return;
   }
   if(n > 2)
   {
    for(i=0;i<n;i++)/* #a  */
    {
     t= -1;
     for(j=0;j<n;j++)
      if(j != i)
       C1[++t] = C[j];
/*     printf("\ncount = %d  t= %d Elements of C1 are: ",count,t);
     for(j=0;j<=t;j++)
      printf("  %c",C1[j] );   */
     comb(n-1,C1,S1);
/*     printf("\ncount = %d  Inside comb itself   n-1 = %d",++count,n-1);
     for(e=0;e< fact(n-1) ;e++)
      { printf("\n");
        for(j=0;j< n-1;j++)
        printf("%c",S1[e][j]);
      }  */
     for(j= i*fact(n-1) ;j< (i+1)*fact(n-1) ;j++)
      { S[j][0] = C[i];
        for(u=0;u<n-1;u++)
	 S[j][u+1]=  S1[j - i*fact(n-1)][u];
      }
     }/* END of for #a  */
     return;
   }
}


[/c]

i have reduced MAX and increased MAX1.
If i increase the value of MAX the prog doesn't run in my comp.
Now im my computer i can run for string of max length 8(earlier it was 6)
But now the judge says compiler error(earlier it was run time error time error).

I can compile in my red hat linux 7.2
with only a warning.I don't think this is a problem.Because in another prob i had used gets and there also was this warning.
AND the judge accepted the prog.

I don't understand what r u saying abt the while loop.
I CAN RUN the PROG IN MY COMP NICELY [/i][/c][/code]

[cyfra]

Hi!

Sorry but this time your program also gave Runtime Error SIGSEGV.

It is because You have too big array S[max1,max]...

When your program tries to run function func and max1=50000 then you have SIGSEGV...

But I wonder how are you solving this task, because there is a simple solution...

If you know it you'd better use if you don't know it write me e-mail or Private Message or just write it here and I will explain you this solution ...

Because it needs only one dimensional array[1..max] where max = length of the word..

Good Luck

[Picard]

i've sent in your program and it was complied successfuly. as Ivor said before: the MAX have to be set to 100 because the judge has >90 long test cases. i advise try to eliminate the store of the result strings in memory. for example here is a very simple "comb" function for generating all permutations (it doesn't solve the problem, the same solutions have to be filtered, but if C[] is sorted then the generated strings are sorted too)
[c]
...
comb(0,t+1,S)
...

void comb(int pos,int n,char C[])
{
static char S[MAX];
if (pos==n)
{
S[pos]=0;
printf("%s\n",S);
}
else
for (int i=0;i<n;++i)
if (C)
{
S[pos]=C;
C=0; //mark as used
comb(pos+1,n,C);
C=S[pos]; //restore
}
}
[/c]

[taj79]

In the word taken from the input file, some letters may appear more than once. For a given word,
your program should not produce the same word more than once
this is what the problem says.

your algo just creates all the combination but
fails to check the above statement

that's why i had used double array S[][]
to store all the comb and printing the strings only once.

what i m failing is to check the repeat occurence of any string in the comb function itself.
Please help me out

[taj79]

i have chenged my prog. but on running it gets into some infinite loop while it is in quicksort function.
Please help me.

Code: Select all

[c]

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX 100
#define MAX1 50000


void comb(int *count,int pos,int n,char C[],char SO[][MAX]);
void quicksort(char SO[][MAX],int n,int p,int r);
int  partition(char SO[][MAX],int n,int p,int r);

main()
{ int i,n,t,count,k;
  char S[MAX],SO[MAX1][MAX];

 gets(S);
 n = atoi(S);
  printf(" %d\n",n);
 for(i=0;i<n;i++)
  { gets(S);/* printf("\n %s",s); */
    t=-1;
    do{
       if(S[++t] == '\0')
       { --t;
        break;
       }
      }while(S[t] != '\0');
      count = -1;
     printf("\n %s",S);
      printf("\n i = %d    t= %d\n",i,t);
     comb(&count,0,t+1,S,SO);/* make all the combinations */
     printf("\n  After comb()\n");
     printf("%d\n",count);
    for(k= 0;k<=count;k++)
     printf(" %s\n",SO[k]);
    quicksort( SO, t+1, 0, count);
    for(k= 0;k<=count;k++)
     {
      if(k=0 || k>0 && strcmp(SO[k],SO[k-1])!= 0 )
       printf("%s\n",SO[k]);
     }

 /*     if(i != 0)
       printf("\n");
    func(s,t);  */
  }

}


void comb(int *count,int pos,int n,char C[],char SO[][MAX])
  {int i,j,q;

               static char S1[MAX];
              printf("\n    Entered comb()\n");
               if(pos==(n))
                  {
                     S1[pos]=0;
		    /* printf("\n Before calling check()\n");
                      for(i=0;i<n;i++)
		       printf(" %c",S1[i]);
		      printf("\n");  */
			++(*count);
		      printf("%s\n",S1);
		       for(j=0;j<n;j++)
		        SO[*count][j] = S1[j];

                   }

               else
	         for( i=0;i<n;++i)
                if(C[i])
                        {
                           S1[pos]=C[i];
                           C[i]=0;         /*mark as used  */
                           comb(count,pos+1,n,C,SO);
                           C[i]=S1[pos];   /* restore  */
                        }

   }

void quicksort(char SO[][MAX],int n,int p,int r)
  {int q,k;
   printf("\n Entered quicksort");
   printf("          p = %d    r = %d",p,r);
   if(p < r){ /*    ++count;
      printf("%d",count);  */
       q = partition(SO,n,p,r);
       printf("\n     q = %d p=%d   r=%d",q,p,r);
       for(k= p;k<=r;k++)
     printf(" %s\n",SO[k]);
        //exit(1);

       quicksort(SO,n,p,q);
       quicksort(SO,n,q+1,r);
       }
       return;
   }

int  partition(char SO[][MAX],int n,int p,int r)
   {
     int i,j,k;
     char S[MAX],u[MAX];
    printf("\n Entered partition");
    printf("          p = %d    r = %d",p,r);
     for(k=0;k<n;k++)
      S[k] = SO[p][k];
     /* x = A[p];  */
     i = p-1;
     j = r+1;
     while(1){
            do{--j;
	      }while(strcmp(SO[j],S) > 0);
	    do{ ++i;
	      }while(strcmp(SO[i],S) < 0);
	    if(i < j)
	    { for(k=0;k<n;k++)
               u[k] = SO[i][k];

              for(k=0;k<n;k++)
               SO[i][k] = SO[j][k];

	      for(k=0;k<n;k++)
                SO[j][k]= u[k];
	    }
	    else
	     return(j);
	     }
   }








[/c]

[Picard]

many bugs:

1. in partition() put an end condition in the do while cycles (before strcmp put 'i<j &&')

2. you have to close all strings with terminating zeros. comb() and partition()

3. there is a 'k=0' of the main()'s if which should be 'k==0'

4. strcmp doesn't work here (stricmp either). you have to put upper case letters before the corresponding lower case letter

hint1: why don't you use C library qsort() function?
hint2: why not sort the initial string (as in your first version), and modify comb() to skip a letter if it's same as the last letter used.

[taj79]

I couldn't understand your suggestions:

1. what;'s the need of putting i<j
in the do while cycles.
i have read quicksort from
Introduction to algorithms by Cormen,Leiserson
no such thing was there.

2.what's the need of putting terminating 0s

4.Check this in a prog:
printf("\n %d\n",strcmp("sadf","sAdf") );
strcmp is working fine with both capital & small letters.

i was unable to understand how to use qsort() library function.
that's why i have made quicksort function.

The problem with my earlier prob is that it fails to run when the number of chars in a string becomes large say >9.
this new prog is better i suppose.

please help me out

[Picard]

you are absolutly right about qsort, you don't need the extra stop conditions.

you have to close the strings with '\0' charachter otherwise strcmp and printf may go further in memory as neccessary (ofcoz the initial memory could be filled with zeros, but you can't rely on that)

strcmp("Baa","aaB")<0 but in the output "aaB" should precede "Baa". you can't use stricmp either, because "Aab" and "aAb" would equal but the problem needs "Aab" always ahead (qsort may put "aAb" first).

[taj79]

I have changed little bit as per your advice but the problem remains the same.
Regarding strcmp i don't think you have said the right thing.
You can check in the 2nd printf statement of my main func by removing the comment sign before exit(1)
here is the changed prog:

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX 100
#define MAX1 50000


void comb(int *count,int pos,int n,char C[],char SO[][MAX]);
void quicksort(char SO[][MAX],int n,int p,int r);
int  partition(char SO[][MAX],int n,int p,int r);

main()
{ int i,n,t,count,k;
  char S[MAX],SO[MAX1][MAX];

 gets(S);
 n = atoi(S);
  printf(" %d\n",n);
  printf("\n CHECK %d\n",strcmp("aAb","Aab") );//exit(1);
 for(i=0;i<n;i++)
  { gets(S);/* printf("\n %s",s); */
    t=-1;
    do{
       if(S[++t] == '\0')
       { --t;
        break;
       }
      }while(S[t] != '\0');
      count = -1;
     printf("\n %s",S);
      printf("\n i = %d    t= %d\n",i,t);
     comb(&count,0,t+1,S,SO);/* make all the combinations */
     printf("\n  After comb()\n");
     printf("%d\n",count);
    for(k= 0;k<=count;k++)
     printf(" %s\n",SO[k]);//exit(1);
    quicksort( SO, t+1, 0, count);
    //qsort(SO,count,t+1);
    for(k= 0;k<=count;k++)
     {
      if(k==0 || k>0 && strcmp(SO[k],SO[k-1])!= 0 )
       printf("%s\n",SO[k]);
     }

 /*     if(i != 0)
       printf("\n");
    func(s,t);  */
  }

}


void comb(int *count,int pos,int n,char C[],char SO[][MAX])
  {int i,j,q;

               static char S1[MAX];
              printf("\n    Entered comb()\n");
               if(pos==(n))
                  {
                     S1[pos]=0;
		    /* printf("\n Before calling check()\n");
                      for(i=0;i<n;i++)
		       printf(" %c",S1[i]);
		      printf("\n");  */
			++(*count);
		      printf("%s\n",S1);
		       for(j=0;j<n;j++)
		        SO[*count][j] = S1[j];
		     SO[*count][n] = '\0';

                   }

               else
	         for( i=0;i<n;++i)
                if(C[i])
                        {
                           S1[pos]=C[i];
                           C[i]=0;         /*mark as used  */
                           comb(count,pos+1,n,C,SO);
                           C[i]=S1[pos];   /* restore  */
                        }

   }

void quicksort(char SO[][MAX],int n,int p,int r)
  {int q,k;
   printf("\n Entered quicksort");
   printf("          p = %d    r = %d",p,r);
   if(p < r){ /*    ++count;
      printf("%d",count);  */
       q = partition(SO,n,p,r);
       printf("\n     q = %d p=%d   r=%d",q,p,r);
       for(k= p;k<=r;k++)
     printf(" %s\n",SO[k]);
        //exit(1);

       quicksort(SO,n,p,q);//exit(1);
       quicksort(SO,n,q+1,r);//exit(1);
       }
       return;
   }

int  partition(char SO[][MAX],int n,int p,int r)
   {
     int i,j,k;
     char S[MAX],u[MAX];
    printf("\n Entered partition");
    printf("          p = %d    r = %d",p,r);
     for(k=0;k<n;k++)
      S[k] = SO[p][k];

     /* x = A[p];  */
     i = p-1;
     j = r+1;
     while(1){
            do{--j;
	      }while(strcmp(SO[j],S) > 0);
	    do{ ++i;
	      }while(strcmp(SO[i],S) < 0);
	    if(i < j)
	    { for(k=0;k<n;k++)
               u[k] = SO[i][k];

              for(k=0;k<n;k++)
               SO[i][k] = SO[j][k];
	     SO[i][n] = '\0';

	      for(k=0;k<n;k++)
                SO[j][k]= u[k];
             SO[i][n] = '\0';
	    }
	    else
	     return(j);
	     }
   }

[Picard]

partition() has still an unterminated string: S[]

about strcmp: read carefully. "aAb" vs "Aab" was an example against stricmp. "Baa" vs "aaB" was the example against strcmp. the rules sais: "An upper case letter goes before the corresponding lower case letter". this means you should use a character order: 'A'<'a'<'B'<'b'<'C'<'c'....

what i was earlier suggested is that you don't have to store and sort the generated strings. just modify the comb function: skip the current letter if it's the same as the last letter used (in this recursive level). ofcoz this solution requires a presort of the string passed to cumb()