195 - Anagram

[ahanys]

May somebody explain me how create a recursive function which solve this problem.
Thanks in advance.

[Shahid]

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]

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]

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]

Shahid: Lines not longer than 5000.

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

Stefan

[pochmann]

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]

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]

Linux / g++

[Shahid]

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]

Read the problem description carefully about the order of the 52 characters.

Your output for baBACc is wrong, for example.

Stefan

[C8H10N4O2]

Are you talking about my sorting?

[Stefan Pochmann]

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]

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]

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]

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.