## 195 - Anagram

Moderator: Board moderators

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
[c]for (i=1; i <= len; i++)
printf("%c", tstr);
printf("\n");[/c]
The actual algorithm is right, but you're output method is too slow. Try to use one function call instead of say, 10 per generated word.

When I used your loop, "abcdefghi" took about 1.5 seconds. When I changed it into one statement, it took 0.13 seconds.

harshahs
New poster
Posts: 8
Joined: Wed Oct 22, 2003 3:58 pm
Hello,

I remove the for loop which i was using for output and instead used

[c]printf("%s\n",&tstr);[/c]

This seems significantly faster, but still I am getting TLE on oj.

I only know exponential algorithm for generating permutations. Is there any faster algorithm or can this code be still optimised to solve it in less time.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
Well if you know how to use C++ STL, there is a function called
next_permutation( a, a+ n );

which will enable you to generate permutations fast enough for words of length 10.

It normally does so in lexicographical order according to the ASCII character code. Since this is a special situation,
you should use the following format.

next_permutation(a, a+n, comp)
wheere comp should be defined as follown:

bool comp(char a, char b)
{
if ( a<b) return true;
return false;

}

Of course the way you define a<b is not as simple as above for this problem. Since a<Z , according to this problem, eventhough this is not the general case with ASCII character set.

harshahs
New poster
Posts: 8
Joined: Wed Oct 22, 2003 3:58 pm
The problem is I am not familiar with C++.
When next_permutation() STL can be implemented in a faster way, I think we can also do the same using C code.

Can I get how the next_perumutation STL is implemented on the net?
If you come across any such thing do help me to make my code more faster.

Thank You
Harsha

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:
harshahs, u can visit the following link for efficiently generating permutation.

http://www.cs.byuh.edu/~johnsonj/permut ... ubmit.html

u can also find a good algirhtm named generating fast sorted permutation in discrete mathematics book.

Frostina
New poster
Posts: 23
Joined: Mon Dec 15, 2003 5:21 am

### Why #195 is WA :~~~

Plz help :~~~

[c]#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define NN 1000
int len, x;
char ans[NN];
struct set {
char ch;
int fre;
}data[NN];
void visit(int n) {
int i;
if (n<len) {
for (i=0;i<x;i++)
if (data.fre) {
ans[n] = data.ch;
data.fre--;
visit(n+1);
data.fre++;
}
}
else {
ans[len] = '\0';
puts(ans);
}
}
int main(void) {
int n, i, j, ni, nj, index;
char str[NN], tmp;
gets(str);
n = atoi(str);
for (;n;n--) {
gets(str);
for (i=0;i<strlen(str);i++)
for (j=i+1;j<strlen(str);j++) {
ni = (str>='a'&&str<='z')? (str-'a') : (str-'A');
nj = (str[j]>='a'&&str<='z')? (str[j]-'a') : (str[j]-'A');
if ((ni>nj)||(ni==nj&&str>str[j])) {
tmp = str[i];
str[i] = str[j];
str[j] = tmp;
}
}
for (i=index=0;i<strlen(str);i++) {
for (j=0;j<i;j++)
if (str[i]==data[j].ch) {
data[j].fre++;
break;
}
if (j>=i) {
data[index].ch = str[i];
data[index].fre = 1;
index++;
}
}
len = strlen(str);
x = index;
visit(0);
}
return 0;
} [/c]
Thanks for your help ! junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
check these things:

1) Case.. make sure you print them as the same case as the input
2) Duplicates if you are given a string with AAA, there should only be one line of output.

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

### 195 WA Why?

program p195;
var
tests,i,j,n:integer;
s:string;
notfinished:boolean;

procedure perest(n:integer);
var
i,first, second: integer;
ch,temp:char;
begin
first := n-1;
while ((s[first] >= s[first+1]) and (first > 0)) do Dec(first);
if first < 1 then
begin
notfinished := False; Exit;
end;
second := n;
while s[second] <= s[first] do Dec(second);
ch := s[second]; s[second] := s[first]; s[first] := ch;
i := first+1;
while i < (n+first+1)/2 do
begin
temp := s[i]; s[i] := s[n+1+first-i]; s[n+1+first-i] := temp;
i := i + 1;
end;
end;

procedure sort;
var
i,j:integer;
t:char;
begin
for i:=1 to n-1 do
for j:=i+1 to n do
if s[i] > s[j] then
begin
t := s[i] ; s[i] := s[j] ; s[j] := t;
end;
end;

begin
for i:=1 to tests do
begin
n := length(s);notfinished := True;
sort;
while notfinished do
begin
writeln(s);
perest(n);
end;
end;
end.

NightZ-1
New poster
Posts: 8
Joined: Sun Feb 01, 2004 11:47 pm
Location: SP, Brazil
Contact:
Do you clean the strings, before makes the anagram?? (e.g spaces, points... etc) medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

### It seems all right

It seems all right
But anybody, help me!

NightZ-1
New poster
Posts: 8
Joined: Sun Feb 01, 2004 11:47 pm
Location: SP, Brazil
Contact:
Do you sort the letters, like this AaBbCcDdEeFfGgHhIiJj... ???

Try this, :

Code: Select all

``````2
ds  ;/ds';[  ds
a ;; ; ;; // // '''   a a a  a a a a    aa``````
My AC program gives the following output:

Code: Select all

``````dddsss
ddsdss
ddssds
ddsssd
dsddss
dsdsds
dsdssd
dssdds
dssdsd
dsssdd
sdddss
sddsds
sddssd
sdsdds
sdsdsd
sdssdd
ssddds
ssddsd
ssdsdd
sssddd

aaaaaaaaaa``````

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

### Thanks, I have solved at last

Thanks, I have solved at last

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

### 195-Still WA after read all post

hi, i have passed all the input at other post, but still got WA.
1. I sort the input in oder A<a<B<b<C<c....
2. I cleaned the input from invalid character like space, coma, etc
3. my permutation algorithm worked well for problem 10098

here's my code

[c]

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

int arr;

int sort_function(const void *a, const void *b)
{
return (arr[*(char *)a] - arr[*(char *)b]);
}

void swap(char *s, int a, int b)
{
char temp = s[a];
s[a] = s;
s = temp;
}

int next_permute(char *str, int len)
{
int key = len - 1;
int newkey = len - 1;

while ((key > 0) && (str[key] <= str[key-1]))
key--;
key--;

if (key < 0) return 0;

newkey = len - 1;
while ((newkey > key) && (str[newkey] <= str[key]))
newkey--;

swap (str, key, newkey);

len--;
key++;

while(len>key)
{
swap(str,len,key);
key++;
len--;
}

return 1;
}

main()
{
int n, i, j, k, len;
char str, temp;

#ifndef ONLINE_JUDGE
freopen ("195i.txt" , "r", stdin );
freopen ("195.out", "w", stdout);
#endif

for (i = 'A', j = 0; i <= 'Z'; i++, j += 2)
arr = j;
for (i = 'a', j = 1; j <= 'z'; i++, j += 2)
arr = j;

scanf ("%d\n", &n);
for (i = 0; i < n; i++)
{
do { gets(temp); } while (temp == '\0');
for (j = 0, k = 0; temp[j]; j++)
if ((temp[j] >= 'a' && temp[j] <= 'z') ||
(temp[j] >= 'A' && temp[j] <= 'Z'))
str[k++] = temp[j];
str[k] = '\0';
len = strlen (str);
qsort ((void *)str, len, sizeof (str), sort_function);
do
{
printf ("%s\n", str);
}
while (next_permute (str, len));
}
return 0;
}
[/c]

thanks.

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
hi b3yours3lf ...

First :
Your mistake is in next_permute function.

Code: Select all

``````int next_permute(char *str, int len)
{
int key = len - 1;
int newkey = len - 1;

while ((key > 0) && (str[key] <= str[key-1])) // == > here
key--;
key--;

if (key < 0) return 0;

newkey = len - 1;
while ((newkey > key) && (str[newkey] <= str[key])) // ==> here
newkey--;

swap (str, key, newkey);

len--;
key++;

while(len>key)
{
swap(str,len,key);
key++;
len--;
}

return 1;
}
``````
you must compare like this, arr[str[key]] <= arr[str[key-1]], because your sort_compare, compare based on this.

second :

Code: Select all

``do { gets(temp); } while (temp == '\0');``
in your input, you just try like this :

Code: Select all

``scanf("%s", temp);``
because the same reason like third :d:d

third :

Code: Select all

``````      for (j = 0, k = 0; temp[j]; j++)
if ((temp[j] >= 'a' && temp[j] <= 'z') ||
(temp[j] >= 'A' && temp[j] <= 'Z'))
str[k++] = temp[j];
str[k] = '\0';
``````
you didn't need that line, because test data not include character other than (A..Z and a..z).

good luck ...

samueljj
New poster
Posts: 18
Joined: Fri Jul 18, 2003 5:24 am
I'm getting WA too. What is the problem with this code? Is there any criticial input that it fails to compute [c]
#include <stdio.h>
#include <string.h>
#define SIZE 500

char word[SIZE],temp[SIZE];
int map[SIZE],l=0;

void arrange(int n){
int i,j;
char temp;
for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
if(word>word[j])
{
temp =word;
word=word[j];
word[j]=temp;
}
}
}
}

void Generator(int n){
int i=0;
char lastentry='0';
if(l==n)
{
temp[l]='\0';
printf("%s\n",temp);
return;
}
for(i=0;i<n;i++)
{
if(!map)
{

if(lastentry!='0'){
if(lastentry!=word)
{
map=1;
temp[l]=word;
lastentry=word;
l++;
Generator(n);
map=0;
l--;
}
}
else
{
map=1;
temp[l]=word[i];
lastentry=word[i];
l++;
Generator(n);
map[i]=0;
l--;
}
}

}

return ;
}

int main(){

int n,l=0;
for(n=0;n<SIZE;n++)
{
map[n]=0;
}
scanf("%d",&n);
while(n!=0)
{
scanf("%s",word);
l=strlen(word);
arrange(l);
Generator(l);
n--;
}
return 0;
}
[/c]
novice programmer