## 195 - Anagram

Moderator: Board moderators

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
congratulations!
and what was the problem,Roby?

Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:
My comparison function did wrong comparison. So, I changed the comparison function into this one:

Code: Select all

``````int comparer( const void * a, const void * b )
{
char * va = ( char * ) a;
char * vb = ( char * ) b;
char bigA, bigB;

bigA = islower(*va) ? (*va)-32 : (*va);
bigB = islower(*vb) ? (*vb)-32 : (*vb);

if ( bigA != bigB )
return bigA-bigB;
else
return (*va)-(*vb);
}``````
And my problem is gone forever

My program was failed with this input:

Code: Select all

``````1
AaB``````
It should produce these:

Code: Select all

``````AaB
ABa
aAB
aBA
BAa
BaA``````
But the fact, my program was producing different output.

Once again thanx for your help (especially for the hint to use islower function, it's inspiring me much)

Daredevil
New poster
Posts: 19
Joined: Tue Apr 01, 2003 7:47 am
Location: Earth

### 195 - Anagrams Why WA?

I don't understand why WA.

Here's my code:

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

int count,n,len;
char num[200],string[300],s[300];

void permute(){
int i;

/*Uppercase letters*/

for(i=65;i<91;i++){
if(num){
string[count++]=i;
num--;
if(count==len) printf("%s\n",string);
else permute();
num++;
string[--count]=0;
}
}

/*lowercase letters*/

for(i=97;i<123;i++){
if(num){
string[count++]=i;
num--;
if(count==len) printf("%s\n",string);
else permute();
num++;
string[--count]=0;
}
}
}

void main(){
int i;
scanf("%i",&n);
while(n--){
scanf("%s",&s);
len=strlen(s);
for(i=0;i<len;i++) num[s]++;
permute();
memset(num,0,190);
}
}

/*end of code*/

New poster
Posts: 22
Joined: Sun Jan 01, 2006 1:43 pm
"the words should be output in alphabetically ascending order".
check this input:
1
aB

output:
aB
Ba

Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:
in this problem the order is A,a,B,b......

Rocky

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil
hello, how to avoid repeated permutations?

Code: Select all

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

#define MAX_SIZE 10000

void swap( char *x, char *y )
{
char tmp = *x;
*x = *y;
*y = tmp;
}

int ch_cmp( const void *a, const void *b )
{
return *((char *)a) - *((char *)b);
}

int fact( int n )
{
return (n == 1) ? 1 : n*fact(n-1);
}

void next_permutation( char *seq, int last )
{
int j, k, r, s;

j = last-1;
while( seq[j] > seq[j+1] ) j--;

k = last;
while( seq[j] > seq[k] ) k--;
swap( &seq[j], &seq[k] );

r = last;
s = j + 1;
while( r > s )
{
swap( &seq[r], &seq[s] );
r--;
s++;
}
}

int main()
{
char seq[MAX_SIZE] = {0};
int slen, np, ntest;

scanf( "%d", &ntest );
while( ntest-- )
{
scanf( "%s", seq );
slen = strlen(seq);
qsort( seq, slen, sizeof(char), ch_cmp );
np = fact(slen)-1;
printf( "%s\n", seq );
while( np-- )
{
next_permutation( seq, slen-1 );
printf( "%s\n", seq );
}
}

return 0;
}
``````
thanks
"A machine can do the work of fifty ordinary men, but no machine can do the work of one extraordinary man.", Shahriar Manzoor

harrym
New poster
Posts: 5
Joined: Thu Sep 07, 2006 8:48 pm
You should use the <algorithm> library, as in
sort(seq,seq+slen,ch_cmp);
....
while(next_permutation(seq,seq+slen,ch_cmp))

next_permutation will permute all elements between the 2 pointers (arg0,arg1) either by operator< or by arg2 (if provided) and will return 0 when there is no lexicorgraphicly next_permutation possible.

acm4fun
New poster
Posts: 1
Joined: Sat Jan 20, 2007 9:22 am

### 195 - TLE??

I got TLE in anagram...

Here is my solution (in C++):
1) use a vector to store all characters of string input,
2) sort the character using sort()
3)

do {

// form a string from characters
// if the string is not found in a vector of "appeared string"
// print it out, store the string in "appeared string"

} while (next_permutation(...))

Will the above algorithm cause TLE? Thanks...!!

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
yes, you will need to do permutation with repetition smarter, and generate them in a manner that you don't need to worry about re-appearance. i.e.: The way they are generated is such that no word will reappear, even if the input has multiple copies of the same letter.

Astimodeus
New poster
Posts: 2
Joined: Mon May 07, 2007 10:47 pm

### 195 Compiler Error

I get this compiler output:

Code: Select all

``````05565437_24.c: In function `prenditesto':
05565437_24.c:53: parse error before `char'
05565437_24.c:56: `arg' undeclared (first use in this function)
05565437_24.c:56: (Each undeclared identifier is reported only once
05565437_24.c:56: for each function it appears in.)
05565437_24.c: In function `purge':
05565437_24.c:68: parse error before `int'
05565437_24.c:71: `i' undeclared (first use in this function)
05565437_24.c:73: `res' undeclared (first use in this function)
``````
with this C code:

Code: Select all

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

int len=0;

void purge(char *arr);
void prenditesto();
void permuta(char *parola, int n);
void stampa(char *parola);

int main()
{
prenditesto();
return 0;
}

void permuta(char *parola, int n)
{
if(n==len-1)
stampa(parola);
else
{
int i;
for(i=n;i<len;i++)
{
int temp = parola[i];
parola[i] = parola[n];
parola[n] = temp;
permuta(parola,n+1);
temp = parola[i];
parola[i] = parola[n];
parola[n] = temp;
}
}
}

void stampa(char *parola)
{
int i;
for(i=0;parola[i]!='\0';i++)
{
printf("%c", parola[i]);
}
printf("%c", '\n');
}

void prenditesto()
{
int num;
int i;
scanf("%d", &num);
char *arg[num];
for(i=0;i<num;i++)
{
scanf("%s", arg[i]);
}
for(i=0;i<num;i++)
{
purge(arg[i]);
permuta(arg[i],0);
}
}

void purge(char *arr)
{
len=strlen(arr);
int i;
char res[len];

for(i=0;i<len;i++)
{
res[i]=arr[i];
}
arr=res;
}``````
I'm puzzled, can you help me out?

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Code: Select all

``char *arg[num]; ``
You can not declare array like this. num must be a constant, or you need to allocate memory dynamically by using malloc().

The code will however compile if you specify C++ as the language.

reemuskumar
New poster
Posts: 4
Joined: Wed Jun 14, 2006 3:55 pm

### pbm 195

What is wrong with this code ? I'm getting signal error while submitting, it is runs fine in my system. Pls let me know what is the stress input.

Code: Select all

``````#include <iostream>
#include <cstring>
#include <cstdlib>

using namespace std;

int charmap[256];
void print_str(char*);

class node {
private:
char data[100];
node *next;

public:
};

private:
node *first;

public:
void insert(char *);
void destroy();
void display();
};

node *tmp;

tmp=new node();
strcpy(tmp->data,str);
tmp->next=first;

if(first==0) {
first=tmp;
return;
}

if(strcmp(first->data,tmp->data)==0) return;

if(strcmp(first->data,tmp->data)>0) {
tmp->next=first;
first=tmp;
return;
}

node *curr=first;

while(curr->next && strcmp(curr->next->data,tmp->data)<0) {
curr=curr->next;
}

if(curr->next && strcmp(curr->next->data,tmp->data)==0) return;
if(strcmp(curr->data,tmp->data)==0) return;
tmp->next=curr->next;
curr->next=tmp;
}

for(node *curr=first;curr;curr=curr->next)
print_str(curr->data);
}

node *curr=first,*next;

while(curr) {
next=curr->next;
delete curr;
curr=next;
}
first=0;
}

void swap(char *str, int x, int y) {
char tmp=str[x];
str[x]=str[y];
str[y]=tmp;
}

void print_str(char *str) {
int len=strlen(str);

for(int i=0;i<len;i++)
for(int j=0;j<charmap[str[i]];j++)
cout<<str[i];
cout<<endl;
}

int comp_char(const void *a, const void *b) {
char *p=(char*)a, *q=(char*)b;
return *p-*q;
}

void HeapPermute(char *str, int n, linklist& l)
{
if (n == 1)
l.insert(str);
else {
for (int i = 0; i < n; i++) {
HeapPermute(str, n-1,l);
if (n % 2 == 1) // if n is odd
swap(str, 0, n-1);
else // if n is even
swap(str, i, n-1);
}
}
}

int main() {
int num;
char word[20][100];

// Get the Number of Words
cin>>num;
for(int i=0;i<num;i++){
cin>>word[i];
}

// Process & Display Anagram for each word
for(int i=0;i<num;i++) {
int len=strlen(word[i]);
for(int j=0;j<256;j++) charmap[j]=0;
for(int j=0;j<len;j++) charmap[word[i][j]]++;
qsort((void*)word[i],len,1,comp_char);
// Shrink word[i];
int r,w=0;
for(r=1;r<len;r++){
if(word[i][w]==word[i][r]) {
} else {
word[i][++w]=word[i][r];
}
}
word[i][++w]=0;
len=strlen(word[i]);
HeapPermute(word[i],len,l);
l.display();
l.destroy();
}
return 0;
}

``````

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Search the board first. Don't open a new thread if there is one already.
Ami ekhono shopno dekhi...
HomePage

Astimodeus
New poster
Posts: 2
Joined: Mon May 07, 2007 10:47 pm
shamim wrote:

Code: Select all

``char *arg[num]; ``
You can not declare array like this. num must be a constant, or you need to allocate memory dynamically by using malloc().

The code will however compile if you specify C++ as the language.
No it won't
Tnx anyway! I've forgot the judge uses a pre c99 compiler

SARKAR
New poster
Posts: 21
Joined: Tue May 22, 2007 4:18 pm

### plzzzzzzz help.......195

MY code is running fine for test cases......
but i am getting WA plzzz see wat is the bug

OR PROVIDE ME WITH SOME CRITICAL TEST CASES

Code: Select all

``code removed``
Last edited by SARKAR on Sat May 26, 2007 5:24 pm, edited 1 time in total.