195 - Anagram

[UFP2161]

Your problem lies here:
[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]

Hello,

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

[c]printf("%s\n",&tstr[1]);[/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]

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]

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]

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]

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]

[junbin]

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]

Help me, please!

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
readln(tests);
for i:=1 to tests do
begin
readln(s);
n := length(s);notfinished := True;
sort;
while notfinished do
begin
writeln(s);
perest(n);
end;
end;
end.

[NightZ-1]

Do you clean the strings, before makes the anagram?? (e.g spaces, points... etc)


Please use tags!!!!!

[medv]

It seems all right
But anybody, help me!

[NightZ-1]

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]

Thanks, I have solved at last

[b3yours3lf]

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[256];

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[201], temp[201];

#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] == '\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[0]), sort_function);
do
{
printf ("%s\n", str);
}
while (next_permute (str, len));
}
return 0;
}
[/c]

thanks.

[Hisoka]

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] == '\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]

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]