Page 1 of 17

Posted: Tue Feb 12, 2002 5:11 pm
by ahanys
May somebody explain me how create a recursive function which solve this problem.
Thanks in advance.

Posted: Fri Feb 22, 2002 1:23 pm
by 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.

Posted: Wed Feb 27, 2002 1:34 pm
by 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.

Posted: Thu Feb 28, 2002 12:18 am
by 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);
}
}

Posted: Thu Feb 28, 2002 6:05 am
by pochmann
Shahid: Lines not longer than 5000.

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

Stefan

Posted: Thu Feb 28, 2002 6:11 am
by 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

Posted: Thu Feb 28, 2002 6:44 am
by 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?

Posted: Thu Feb 28, 2002 6:57 am
by pochmann
Linux / g++

Posted: Thu Feb 28, 2002 12:10 pm
by 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*/

Posted: Thu Feb 28, 2002 12:24 pm
by Stefan Pochmann
Read the problem description carefully about the order of the 52 characters.

Your output for baBACc is wrong, for example.

Stefan

Posted: Fri Mar 01, 2002 3:44 am
by C8H10N4O2
Are you talking about my sorting?

Posted: Fri Mar 01, 2002 8:00 am
by 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

Posted: Fri Mar 01, 2002 8:04 am
by 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.

Posted: Fri Mar 01, 2002 10:01 pm
by Shahid
yup, atlast i understand the problem properly(i think so...:smile:), 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*/

Posted: Fri Mar 01, 2002 10:14 pm
by 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.