## 195 - Anagram

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

ahanys
New poster
Posts: 24
Joined: Mon Nov 19, 2001 2:00 am
Location: N/A
Contact:
May somebody explain me how create a recursive function which solve this problem.
Thanks in advance.

Shahid
Learning poster
Posts: 68
Joined: Fri Oct 26, 2001 2:00 am
Location: Dhaka, Bangladesh
Contact:
HI, do u read the book Discrete Math and Its Apllications by K. H. Rosen?

195 is a permutation type problem.

Read the chapter naming "Generating permutations and combinations" on page 296.

I am sure u can solve that after reading that.

Shahid
Learning poster
Posts: 68
Joined: Fri Oct 26, 2001 2:00 am
Location: Dhaka, Bangladesh
Contact:
in problem 195, can anyone say, that what is the maximum length of the input string?
the limits of this problem is not well defined, i suppose to do all the programming tasks, but got wrong answer.
If there anything in the program without permutation and sorting them lexiographically?
thanx in advance.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA
The input is completely valid. At first, I was getting Output Limit Exceeded because I was printing duplicates. However, I have fixed that problem. Now I get Wrong Answer. Can someone look at my code and help me out?

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

int NtS[50],X[50],L;
bool Z[50];

int compare (const void * a, const void * b)
{
return ( *(int*)a-*(int*)b );
}

void permutate(int n,int O[50],bool U[50])
{
int i,j,k;
int LL;
if(n==L)
{
for(i=0;i<L;i++)
{
if(NtS[O]%2==0)
printf("%c",NtS[O]/2+'A');
else
printf("%c",(NtS[O]-1)/2+'a');
}
printf("n");
return;
}

LL=-1;
for(i=0;i<(L-n);i++)
{
k=0;
while(U[k])
k++;
for(j=0;j<i;j++)
{
k++;
while(U[k])
k++;
}
if(NtS[k]!=NtS[LL])
{
O[n]=k;
U[k]=true;
permutate(n+1,O,U);
LL=k;
U[k]=false;
}
}
}

void main()
{
char B[500];
int i,j,n;

scanf("%dn",&n);
for(j=0;j<n;j++)
{
scanf("%s",B);
for(i=0;i<50;i++)
{
NtS=-1;
X=-1;
Z=true;
}

L=strlen(B);
for(i=0;i<L;i++)
{
if(isupper(B))
NtS=int(B-'A')*2;
else
NtS=int(B[i]-'a')*2+1;
Z[i]=false;
}

qsort (NtS, L, sizeof(int), compare);

permutate(0,X,Z);
}
}

pochmann
New poster
Posts: 28
Joined: Sat Jan 26, 2002 2:00 am
Contact:
Shahid: Lines not longer than 5000.

C8H10N4O2: On my computer, you only output lowercase letters.

Stefan

pochmann
New poster
Posts: 28
Joined: Sat Jan 26, 2002 2:00 am
Contact:
C8H10N4O2: I just saw that you only output the test cases that don't contain 'A'. Maybe a problem with your conversion of 'A' to 0?

Stefan

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA
Please explain some more.
I convert A to 0 and a to 1 and B to 2 and b to 3 in order to sort them. It works fine on my compiler (VC++ 6.0). What platform/compiler are you using?

pochmann
New poster
Posts: 28
Joined: Sat Jan 26, 2002 2:00 am
Contact:
Linux / g++

Shahid
Learning poster
Posts: 68
Joined: Fri Oct 26, 2001 2:00 am
Location: Dhaka, Bangladesh
Contact:
stefan thanx for ur reply. Do u want to ay that the maximum length does not exceed 5000.
i attach my code here. plz help me if anyone have time:

/*@BEGIN_OF_SOURCE_CODE*/

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

void permute(char *in);
int sort_function( const void *a, const void *b);

void main()
{
int num, i , k;
char input[5000], ch;

scanf("%dn", &num);

for(i = 0; i < num; i++)
{
gets(input);

qsort(input, strlen(input), sizeof(input[0]), sort_function);

permute(input);
}
}

void permute(char *in)
{
char ch, prev[5000], tmp;
static char res[5000] = {0};
int c1, c2, len, k, j, i;

puts(in);

if(!strcmp(res, in))
return;

strcpy(res, in);
len = strlen(in);

for(k = len - 1, c1 = in[k-1], c2 = in[k]; k >= 0; k--, c1 = in[k-1], c2 = in[k])
{
if(c1 < c2)
break;

else
continue;
}

if(!k)
return;

j = k;
c2 = in[j];

while((c1 < c2) && (j < len))
{
j++;
c2 = in[j];
}

j--;
tmp = in[j];
in[j] = in[k-1];
in[k-1] = tmp;

qsort(&in[k], strlen(in)-k, sizeof(in[0]), sort_function);

permute(in);
}

int sort_function( const void *a, const void *b)
{
return( strcmp((char *)a,(char *)b) );
}

/*@END_OF_SOURCE_CODE*/

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Read the problem description carefully about the order of the 52 characters.

Your output for baBACc is wrong, for example.

Stefan

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA
Are you talking about my sorting?

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Sorry, no. That was about Shahid's program. Your problem still is that for example with the input

5
aAb
bBc
cCd
aAb
bBc

your output is

Bbc
Bcb
bBc
bcB
cBb
cbB
Ccd
Cdc
cCd
cdC
dCc
dcC
Bbc
Bcb
bBc
bcB
cBb
cbB

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
C8H10N4O2, I think your problem might be that you compare a "character" with it's predecessor at position -1. And if that happens to be a zero and your character is an "A", that's a problem.

So I believe you access data outside of the array, which would explain the different behaviour on your machine.

Shahid
Learning poster
Posts: 68
Joined: Fri Oct 26, 2001 2:00 am
Location: Dhaka, Bangladesh
Contact:
yup, atlast i understand the problem properly(i think so...), but the result is runtimr error in the judge and hang in my local pc.
my modified code is:

/*@BEGIN_OF_SOURCE_CODE*/

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

void permute(int *in, int length);
int sort_function( const void *a, const void *b);
int value[123];

void main()
{
int num, i, j, k = 1, in[500], length;
char input[500], ch = 'A';

for(; ch <= 'Z'; ch++, k+= 2)
{
i = ch;
value = k;
}

k = 2;
ch = 'a';
for(; ch <= 'z'; ch++, k+= 2)
{
i = ch;
value = k;
}

scanf("%dn", &num);

for(i = 0; i < num; i++)
{
gets(input);

length = strlen(input);

for(k = 0; k < length; k++)
{
j = input[k];
in[k] = value[j];
}

qsort(in, length, sizeof(in[0]), sort_function);

permute(in, length);
}
}

void permute(int *in, int len)
{
char anstr[500];
static char res[500] = {0};
int k, j, tmp;

for(k = 0; k < len; k++)
if(in[k]%2)
anstr[k] = 'A' + in[k]/2;
else
anstr[k] = 'a' + in[k]/2 - 1;

anstr[len] = '';

puts(anstr);

if(!strcmp(res, anstr))
return;

strcpy(res, anstr);

for(k = len - 1; k > 0; k--)
{
if(in[k-1] < in[k])
break;

else
continue;
}

if(!k)
return;

j = k;

while((in[k-1] < in[j]) && (j < len))
j++;

j--;
tmp = in[j];
in[j] = in[k-1];
in[k-1] = tmp;

qsort(&in[k], len-k, sizeof(in[0]), sort_function);

permute(in, len);
}

int sort_function( const void *a, const void *b)
{
return( strcmp((char *)a,(char *)b) );
}

/*@END_OF_SOURCE_CODE*/

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA
Thanks for the tip. I fixed that bug but it still gives me Wrong Answer. I used your data set which currently produces:

Aab
Aba
aAb
abA
bAa
baA
Bbc
Bcb
bBc
bcB
cBb
cbB
Ccd
Cdc
cCd
cdC
dCc
dcC
Aab
Aba
aAb
abA
bAa
baA
Bbc
Bcb
bBc
bcB
cBb
cbB

Code: Select all

/*   @JUDGE_ID:   3134MC   195   C++   "Permutation"   */

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

int compare (const void * a, const void * b)
{
return ( *(int*)a-*(int*)b );
}

void permutate(int n,int L,int O[50],bool U[50],int NtS[50])
{
int i,j,k;
int LL=-1;
if(n==L)
{
for(i=0;i<L;i++)
{
assert(O[i]<L);
assert(O[i]>=0);
if(NtS[O[i]]%2==0)
printf("%c",NtS[O[i]]/2+'A');
else
printf("%c",(NtS[O[i]]-1)/2+'a');
}
printf("n");
return;
}

for(i=0;i<(L-n);i++)
{
k=0;
while(U[k])
k++;
for(j=0;j<i;j++)
{
k++;
while(U[k])
k++;
}
assert(k<L);
assert(k>=0);
assert(LL<L);
if((LL==-1)||(NtS[k]!=NtS[LL]))
{
O[n]=k;
LL=k;
U[k]=true;
permutate(n+1,L,O,U,NtS);
U[k]=false;
}
}
}

void main()
{
char B[500];
int i,j,n;
int X[50],L;
int NtS[50];
bool Z[50];

scanf("%dn",&n);
for(j=0;j<n;j++)
{
scanf("%s",B);

L=strlen(B);
for(i=0;i<L;i++)
{
if(isupper(B[i]))
NtS[i]=int(B[i]-'A')*2;
else
NtS[i]=int(B[i]-'a')*2+1;
Z[i]=false;
}

qsort (NtS, L, sizeof(int), compare);

permutate(0,L,X,Z,NtS);
}
}
If you have a better test data set, I would love to see it. Also, if you have any idea, I would be very grateful. I have been working on this program for 2 weeks and I keep getting the same results.