195 - Anagram

[serur]

congratulations!
and what was the problem,Roby?

[Roby]

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]

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*/

[taskin]

"the words should be output in alphabetically ascending order".
check this input:
1
aB

output:
aB
Ba

[Rocky]

in this problem the order is A,a,B,b......

Rocky

[beloni]

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

[harrym]

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]

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]

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]

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]

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]

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:
                friend class linklist;
};

class linklist {
        private:
                node *first;

        public:
                linklist():first(0){}
                void insert(char *);
                void destroy();
                void display();
};

void linklist::insert(char *str) {
        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;
}

void linklist::display() {
        for(node *curr=first;curr;curr=curr->next)
          print_str(curr->data);
}

void linklist::destroy() {
        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];
  linklist l;
  
  // 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]

Search the board first. Don't open a new thread if there is one already.

[Astimodeus]

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]

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