195 - Anagram

[deddy one]

hmmm, I misunderstood the problem statement about the ascending order
thx red scorpion, now I know why I get WA.

only one problem lie now == > how to code it right

I tried to fix my code but still couldn't get the result as same as
your. can you tell me hints to solve this

[anupam]

right you are.

[Red Scorpion]

Hi, Try to sort Acending A-a-B-b-C-c-D-d-E-e-...
using array, like this:

[code]
st['A'] = 1
st['a'] = 2
st['B'] = 3
st['b'] = 4
st['C'] = 5
st['c'] = 6

And using this array to sort the string.
Hope this helps. [/code]

[VitorRodrigues]

yeah. that's just the solution. i was getting WA because i've not noticed that particular question. now i've got AC.

Thanks everybody

[razibcse]

I followed the same ascending order as u guys..but getting WA...

I don't find any error in my code..one problem may be in determining
the factorial of the length of the string...
I didn't find statement about what's the maximum size of the string..
please explain it to me...I used double to calculate factorial and converted it to unsigned long...is it right?
however, here's my code:

Code: Select all

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#define MAX 200
#define MAXSZ 60

int comp(const void *a,const void *b);
void permutation(long arr[],long n);
unsigned long fac(long n);

long m,to_div[MAX];
char letter[]={'0','A','a','B','b','C','c','D','d','E','e','F','f','G','g','H',
'h','I','i','J','j','K','k','L','l','M','m','N','n','O','o','P','p','Q','q','R',
'r','S','s','T','t','U','u','V','v','W','w','X','x','Y','y','Z','z'};
void main()
{

long n,a,len,i,j,count[MAX],num[MAX];
char str[MAX];

scanf("%ld",&n);
for(a=0;a<n;a++)
 {
 for(i=0;i<MAXSZ;i++)
   {
   count[i]=0;
   num[i]=0;
   }
 scanf("%s",str);
 len=strlen(str);

 for(i=0;i<len;i++)
   for(j=1;j<MAXSZ;j++)
      if(str[i]==letter[j])
        {
        num[i]=j;
        break;
        }


 for(i=0;i<len;i++)
   count[num[i]]++;

 j=0;
 for(i=1;i<MAXSZ;i++)
   if(count[i]>1)
      to_div[j++]=count[i];
 m=j;

 

 qsort((void *)num, len, sizeof(num[0]), comp);
 permutation(num,len);

 }
}

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

void permutation(long arr[],long n)
{
long a,j,k,r,s;
unsigned long x,factorial;
long temp;
factorial=fac(n);

for(a=0;a<n;a++)
   printf("%c",letter[arr[a]]);
   printf("\n");
for(x=1;x<factorial;x++)
 {
 j=n-2;
 while(arr[j]>=arr[j+1])
   j--;

 k=n-1;
 while(arr[j]>=arr[k])
   k--;

 temp=arr[j];
 arr[j]=arr[k];
 arr[k]=temp;

 r=n-1;
 s=j+1;
 while(r>=s)
   {
   temp=arr[r];
   arr[r]=arr[s];
   arr[s]=temp;

   r--;
   s++;
   }

 for(a=0;a<n;a++)
   printf("%c",letter[arr[a]]);
   printf("\n");
 }

}

unsigned long fac(long n)
{
double pro;
long a,b;
unsigned long fact;

pro=1;
for(a=2;a<=n;a++)
  pro*=a;
for(a=0;a<m;a++)
  for(b=to_div[a];b>=2;b--)
   pro/=b;
fact=(unsigned long)pro;
return fact;
}

[Observer]

I would like to learn some efficient algorithms/methods to generate permutations and combinations.

When using my own algorithm, I always get TLE for both 195 and 10098......

Please, could anyone share their thoughts or algorithms with me?

It's hard for me to find related online resources, as I know nothing about programming languages other than Pascal.

So please help!!!

Or, you may introduce some good books or resources to me.

Thanks very much!!

[Maxim]

I use algorithm for finding next permutation of some sequence A. Let n denote length of A. Find such A and A[j] elements that satisfy condition A < A[j], where i < j. If there are no such two elements, there is no next permutation. Otherwise, exchange these two elements and reverse order of elements A[i + 1] through A[n], i.e. A[i + 1] <-> A[n], A[i + 2] <-> A[n

[steinar]

Try http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz. This is a preview on a chapter on permutations in Knuth's Art of Computer Programming. Should be the definite guide

[steinar]

I just like to point out an alternative to using the array with st[0] = 'A', st[1] = 'a', etc. I would recommend a function, like this one:

bool isLower(char a, char b)
{
if (tolower(a) == tolower(b)) return (a < b);
else return (tolower(a) < tolower(b));
}

It gives the order you're looking for, and is (in my opinion) cleaner programming.

[deddy one]

Hi try to search SEPA algoithm on the net resources

[Observer]

Thx for all your help!

Now I know how to generate permutations in reasonable time! Thx a lot!

For folks trying to solve Q195, be careful:
the order of the letters is
A -> a -> B -> b -> C -> c -> ... -> Z -> z

[Nick]

The judge's input positively more than 30 chars...my mistake was the size of the array was too small.

Thanks guys,
nick

[18369AT]

Here is quite efficient (I think) and easy-to-use function that helps to sort characters correctly:

[pascal]
function letval(c:char):integer;
var v:integer;
begin
if upcase(c)=c then
v:=(ord(c)-ord('A'))*2
else
v:=(ord(c)-ord('a'))*2+1;
letval:=v;
end;
[/pascal]

It generates character codes this way: A=0, a=1, B=2, etc.. and they are easy to sort...

[gcp]

Why OLE?


My code:

Code: Select all

[cpp]
#include <iostream.h>
#include <string.h>

char A[100], escreve[100], temp;
int n, marca[1000], cont;

void anagrama()
{
    for (int i=0; i<strlen(A); i++)
     { if (marca[i]==0)
        { escreve[cont]=A[i];
	       cont++;
	       marca[i]=1;
	       if (cont==strlen(A))
	        { escreve[cont]='\0';
	          cout << escreve << endl;
	        }
          anagrama();
	  	 	 marca[i]=0;
	  		 cont--;
        }
    }
}

void main()
{
    cin >> n;

    for (int i=1; i<=n; i++)
    {
		cin >> A;
		for (int c=0; c<1000; c++) marca[c]=0;
      cont=0;

      for (int i=0; i<strlen(A)-1; i++)
       for (int j=i+1; j<strlen(A); j++)
        if (A[j]<A[i])
         { temp=A[j]; A[j]=A[i]; A[i]=temp; }
       anagrama();
    }
}
[/cpp]

Thanks.

[stcheung]

Hi guys, so I submitted like 10 times already and still getting WA for 195. I understand the sorting is A < a < B < b < C < c...and my code also takes care of blank lines. So here is my code, if anyone can kindly test it against some tricky inputs that would be great. Thanks in advance!


[cpp]/* 195 */
#include <iostream.h>
#include <stdlib.h>
#include <string>
#include <algorithm>

string next(string, int);
bool lessthan(char, char);
string mysort(string s, int len);

int main()
{
int numcases;
cin >> numcases;
string s;
getline(cin, s);
for(int i=0; i<numcases; i++)
{
getline(cin, s);
int len = s.length();
s = mysort(s, len);

while(true)
{
cout << s << "\n";
s = next(s,len);
if(s == "")
break;
}
}
return 0;
}

string next(string in, int len)
{
string result="";
char m,n;
int pos1=-1, pos2=-1;
for(int j=len-1; j>=1; j--)
{
n = in[j];
for(int i=j-1; i>=0; i--)
{
m = in;
if(m < n && i > pos1)
{
pos1 = i;
pos2 = j;
}
}
}
if(pos1 != -1)
{
char temp = in[pos1];
in[pos1] = in[pos2];
in[pos2] = temp;
result+=in.substr(0, pos1+1);

char temp2[len - pos1 - 1];
for(int k=pos1+1; k<len; k++)
temp2[k-pos1-1] = in[k];

sort(temp2, temp2+len-pos1-1);
for(int k=0; k<len-pos1-1; k++)
result+=temp2[k];
}
return result;
}

bool lessthan(char a, char b)
{
char a2 = tolower(a);
char b2 = tolower(b);
if(a2 < b2)
return true;
else if(b2 < a2)
return false;
else return (a < b);
}

string mysort(string s, int len)
{
char arr[len];
for(int k=0; k<len; k++)
arr[k] = s[k];
for(int m=0; m<len-1; m++)
{
for(int n=m+1; n<len; n++)
{
if(lessthan(arr[n], arr[m]))
{
char tmp = arr[m];
arr[m] = arr[n];
arr[n] = tmp;
}
}
}
string result="";
for(int z=0; z<len; z++)
result+=arr[z];
return result;
}[/cpp]