## 195 - Anagram

Moderator: Board moderators

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm
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
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
right you are. "Everything should be made simple, but not always simpler"

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
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
New poster
Posts: 9
Joined: Wed Apr 16, 2003 6:50 pm
Location: Braga, Portugal
Contact:
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
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Contact:
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), 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;
}

``````
Wisdom is know what to do next; virtue is doing it.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

### 195 : how to generate fast, sorted permutations/combinations

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.

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

Thanks very much!!   Last edited by Observer on Sun May 11, 2003 1:43 pm, edited 1 time in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:

### Next permutation

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
New poster
Posts: 2
Joined: Sat May 31, 2003 6:22 pm
Location: Iceland

### Text on permutations

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
New poster
Posts: 2
Joined: Sat May 31, 2003 6:22 pm
Location: Iceland
I just like to point out an alternative to using the array with st = 'A', st = '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
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm
Hi try to search SEPA algoithm on the net resources

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

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
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

### yes indeed

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

Thanks guys,
nick

18369AT
New poster
Posts: 1
Joined: Wed Aug 06, 2003 2:07 am

### Function for correct character sorting (195 - Anagram)

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
New poster
Posts: 6
Joined: Sat Nov 22, 2003 5:38 am
Location: Brazil
Contact:

### 195 - OLE

Why OLE?

My code:

Code: Select all

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

char A, escreve, temp;
int n, marca, 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.
VIVA LEOPARDO SC!!

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

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]