Anagramma meghatározása C -vel

C/C++

Segítségre lenne szükségem, hogy C-ben hogyan tudnám, két max. 30 karakteres szóról megállapítani, hogy anagramma é , avagy sem?

( aaron v | 2007. 12. 14., p – 23:47 )

Van valami követelmény arra, hogy hogyan írd meg?
Egy tipp:
Kikötjük, hogy ASCII karakterek lehetnek benne.
Láda-rendezéssel (www.cs.bme.hu/~kiskat/algel/pp3elo.pdf) rendezed a két karaktersorozat tömbjét. (lineáris időben)
Utána a két tömböt összefésülöd. (szintén lináris időben).
Végiglépkedsz az összefésült eredénytömbön és megnézed, hogy egymás után mindig páros számú azonos karakter van-e.
Esetleg az anagramma értelmezésétől függően a szóközöket és az írásjeleket bele sem rakod a rendezett tömbbe. Így ha csak a betűk sorrendjét változtatták meg, minden betűhöz ott lesz a párja. Azért kell páros számú azonos karaktert nézni, hiszen lehet, hogy 2 darab l betű van, akkor nyilván az egymás utáni 4-et is el kell fogadni. (ha jól nézem, az egész megoldható O(n) alatt, nem tudom, hogy milyen tárgyból kell megírni (csak gondolom, hogy beadandó), ez esetleg szempont lehet.
Vagy inkább konkrét kód szintjén érdekelne a megírás módja?
(az ascii karakterek kikötést azért raktam bele, hogy a ládarendezés gyors legyen, de unicode-dal éppúgy lehet ládarendezni, csak ott mondjuk a ládarendezés eléggé pazarló lenne)

( apal v | 2007. 12. 14., p – 23:46 )

Sorbarendezed a betu"it (abc-be), majd az eredmenyeket osszehasonlitod: 


static int char_compare(const void *v1,const void *v2)
{
 if ( *(char *)v1<*(char *)v2 )
    return(-1);
 else
    return(1);
}
is_anagram(char *c1,char *c2)
{
 char *w1,*w2;
 int  r;
 w1=strdup(c1);
 w2=strdup(c2);
 qsort(w1,strlen(w1),1,char_compare);
 qsort(w2,strlen(w2),1,char_compare);
 r=strcmp(w1,w2);
 free(w2);
 free(w1);
 if ( ! r ) 
   return(1);
 else 
   return(0);
}

najo, utf-es kodolasnal lehet baj. akkor elobb atalakitod unicode-16/32-re (iconv()), oszt ugy sorbarendez es osszehasonlit.

A.

( kl3on v | 2007. 12. 14., p – 23:47 )

A felvitt szavakat úgy tárolnám el, hogy a betűket rendezném benne, ezután a megadott szóban is és ha egyezik valamelyikkel, akkor anagramma.

--
Nem győzhetsz. Nem érhetsz el döntetlent. Még csak ki sem szállhatsz a játékból.

( zamboriz v | 2007. 12. 15., szo – 00:34 )

Szerintem nem kell hozzá rendezés: 


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

unsigned char c1[256], c2[256];

void x( unsigned char *c, unsigned char *s ){
  for( int i=0; s[i]; i++ ) c[s[i]]++;
}

int main() {
  x( c1, "index kaszabol" );
  x( c2, "szexbika danol" );
	
  puts( !memcmp( c1, c2, 256 )? "OK, anagramma.\n": "Nem anagramma.\n" );

  return 0;
}

Ha figyelni kell a kis/nagy betűkre, ékezetes karakterekre, írásjelekre, akkor még dolgozni kell kicsit rajta. :-)

Nekem is pont ez jutott eszembe, csak az én megoldásomban csak egy tömb van, a második stringnél csökkentek nem növelek, és így a végén a 0-kat ellenőrzöm...
És elvileg egyezik az anagramma szabályaival. (És igen, még lehetne memóriát spórolni...) 


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

int isAnagram( unsigned char *s1, unsigned char *s2 )
{
  char c[256];
  memset(c,0,256);

  for(int i=0; s1[i]; ++i)
     if (isalpha(s1[i]))
        ++c[tolower(s1[i])];

  for(int i=0; s2[i]; ++i)
     if (isalpha(s2[i]))
        --c[tolower(s2[i])];

  for(int i=0; i<256; ++i)
    if (c[i]!=0)
       return 0;

  return 1;
}

int main() 
{
  puts( isAnagram( "index kaszabol" , "szexbika danol" )? "OK, anagramma.\n": "Nem anagramma.\n" );

  return 0;
}

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

> És az eredeti, a kérdésemben szereplő problémára mi a megoldás?

Először pontosan tisztázni kell a követelményeket. Ékezetes betűk, írásjelek helyes kezelése bonyolultabb kódot igényel, ezért nem mindegy, hogy kell-e ezekkel törődni.

Aztán eldöntöd, hogy rendezéssel, vagy karakter számlálással szeretnéd a problémádat megoldani.

Végül pedig implementálod a megoldást.

Egyszerű :-)))

> de mindig hibákat produkálok csak.

Mindenki így kezdi.

> Biztos, hogy c1 és c2 összes eleme nullával inicializált?

http://www.open-std.org/JTC1/SC22/WG14/www/standards

http://www.open-std.org/JTC1/SC22/WG14/www/docs/n1124.pdf, 138. oldal: 


10 If an object that has automatic storage duration is not initialized explicitly, its value is
indeterminate. If an object that has static storage duration is not initialized explicitly,
then:
— if it has pointer type, it is initialized to a null pointer;
— if it has arithmetic type, it is initialized to (positive or unsigned) zero;
— if it is an aggregate, every member is initialized (recursively) according to these rules;
— if it is a union, the first named member is initialized (recursively) according to these
rules.