Anagramm Programm

[NRj™]

Hi. Ich habe ein Problem mit einem Programm. Die Aufgabenstellung: Erstelle ein Programm das überprüft ob 2 Wörter Anagramme sind oder nicht. Hier der Quelltext:

 Spoiler

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


int main(int argc, char *argv[]) {
	int i, j, length, length2;
	char s1 [100];			//Feld string1
	char s2 [100];			//Feld string2
	
	printf("Anagramm: \n\n");
	printf("Bitte geben Sie zwei Worte ein: \n\n");
	fgets(s1,100,stdin);			//Eingabe Wert string1
	fgets(s2,100,stdin);			//Eingabe Wert string2
	length=strlen(s1);				//Länge von s1 auf length
	length2=strlen(s2);				//Länge von s2 auf length2
	
	for (i = 0; i < length; i++)
	{
		s1[i]=tolower (s1[i]);
	}
								 
	for (j = 0; j < length; j++) {
		s2[j] = tolower (s2[j]);
	}
	
	int pos=strspn(s1,s2);		//Länge Zeichenlänge
		pos=pos-length;
		
	if (pos==0 && length==length2)
	{  
		printf("\nDie beiden Woerter sind Anagramme \n");
	}		
	 	else 
		{
	 		printf("\nDie beiden Woerter sind keine Anagramme");
		}
				
	return 0;
}

Probiert man die Wörter aab und baa oder baa und aba etc. funktioniert alles. Jedoch bei aab und abb nicht. Da zeigt es an, dass es ein Anagramm ist, obwohl das nicht stimmt. Könnt ihr mir helfen?

[warfley]

Das liegt daran das strspn nur überprüft ob die zeichen vorkommen nicht ob die anzahl oder Reihenfolge stimmt. ich würde es etwa so machen:

int isAnagram(char[] s1, char[] s2, int length){
  for (i=0; i<length; i++) 
    if (s1[i]!=s2[length-i-1])
      return 0;
  return -1;
}

[Jeoni]

Die Begründung, warum dein Programm nicht funktioniert, hat warfly schon gegeben. Präsentiert hat er aber eine Funktion, die man eher isPalindrome nennen sollte. Sie prüft nur auf einen Spezialfall eines Anagramms, nämlich dem des Palindroms.

Würde es irgendwie so machen:

int isAnagram(const char* s1, const char* s2, unsigned int length)
{
	unsigned char chars[255]; // count of one char must not exceed 255; assume that even in a string a character can have a value of [0;255]
	memset(chars, 0, sizeof(chars));

	for (unsigned int i = 0; i < length; i++)
	{
		chars[s1[i]]++;
		chars[s2[i]]--;
	}

	for (unsigned int i = 0; i < (sizeof(chars) / sizeof(chars[0])); i++)
		if (chars[i])
			return 0;

	return -1;
}

Wenn genau die gleichen Zeichen (und die gleiche Anzahl für jedes dieser Zeichen) in s1 wie in s2 vorkommen, ist das array "chars" nach der ersten Schleife wieder vollständig mit 0 gefüllt. Ich hoffe, es ist ungefähr klar, was ich meine bzw. dass sich alles andere eh aus dem Quelltext erklärt.
Mit freundlichen Grüßen
Jeoni

[hazejp]

Du könntest das Problem komplett ohne Schleifen lösen:

static int compare_char(const void *x, const void *y) {
  return *((const char*)x) - *((const char*)y);
}

char is_anagram(const char *a, const char *b) {
  int lenA = strlen(a);
  char *cpA, *cpB, res;
  if (strlen(b) != lenA) return 1;
  cpA = strdup(a);
  cpB = strdup(b);
  qsort(cpA, lenA, 1, compare_char);
  qsort(cpB, lenA, 1, compare_char);
  res = strcmp(cpA, cpB);
  free(cpA);
  free(cpB);
  return res;
}

[Jeoni]

Trotz scheinbarer Schleifenlosigkeit der Lösung, ist die Komplexität doch höher.
Die von mir vorgeschlagene Lösung hat eine Komplexitätsklasse von O(N). Mit einem konstanten Faktor bestehend aus der zweiten Schleife und dem memset. Also quasi O(N+c), aber meines Wissens nach schreibt man das so nicht, ist aber vllt. genauer.
Die schleifenlose Lösung hat eine Komplexitätsklasse von O(N*log(N)) (wobei log der Logarithmus zur Basis 2 ist), durch die Verwendung von qsort. Auch hier kann man das wieder genauer spezifizieren mit O(2*N*log(N)+2N). Die 2N kommen aus dem strdup, was intern ja auch letztlich eine Schleife ist, die N mal durchlaufen wird. Die Komplexität von strcmp (also im worst case wieder N) kommt noch hinzu. Abgesehen von der höheren algorithmischen Komplexität kostet das Allokieren (hier in strdup) und Deallokieren auch seine Zeit (allerdings unabhängig von der Stringlänge N), weil dahinter ja letztlich auch irgendwelche Algorithmen sitzen, die für's Heap-Speichermanagement verantwortlich sind.
Auch wenn die Funktion selber tatsächlich schleifenlos ist (Unterfunktionen nicht einbezogen), wollte ich das nur mal anbringen
Mit freundlichen Grüßen
Jeoni

[hazejp]

Tatsächlich zählt mein Programm nicht zu den effizientesten. Tja, das ich habe ich nun von meiner Faulheit... übrigens ist strdup() obiges Beispiel betreffend redundant. Immerhin wäre mit richtig angesetzten Optimierungen "noch" O(N+2N*log(N)) zu erreichen

[NRj™]

Ich dank euch Leute. Leider bin ich nicht auf dem selben Level eurer geposteten codes. So sehr wie ich es versuche sie zu verstehen, es gelingt mir nicht. Und c & p ist nicht der Sinn der Sache.

[warfley]

Originally Posted by Jeoni

Die Begründung, warum dein Programm nicht funktioniert, hat warfly schon gegeben. Präsentiert hat er aber eine Funktion, die man eher isPalindrome nennen sollte. Sie prüft nur auf einen Spezialfall eines Anagramms, nämlich dem des Palindroms.

Stimmt verwechsel die immer

Ich dank euch Leute. Leider bin ich nicht auf dem selben Level eurer geposteten codes. So sehr wie ich es versuche sie zu verstehen, es gelingt mir nicht. Und c & p ist nicht der Sinn der Sache.

Dann versuche ich dir mal den Code von Jeoni zu erklären:

Die Idee ist, ein Ansistring besteht aus Charactern, Byte großen Zahlen von 0 bis 255 (Siehe ASCII Tabelle). Um rauszufinden ob das Wort ein Anagramm ist müssen wir nur überprüfen ob die anzahlen aller einzelnen Buchstaben bei beiden Wörtern gleich sind. Wir zählen also die A's, die B's, etc.
Dafür wird ein Array verwendet welches die Anzahlen sichert. Dieses Array benötigt 255 Felder (für die Zeichen 1..255, 0 darf sowieso nur einmal vorkommen am Ende eines Strings)

unsigned char chars[255];

der Datentyp unsigned char stellt Zahlen zwischen 0 und 255 dar, da du eh nicht mehr buchstaben in deinem Wort haben kannst reicht er völlig aus, der typ könnte natürlich auch int sein.

Nun hat sich Jeoni in seinem Code zunutze gemacht das ein 'A' letztlich nur eine Zahl ist (65), und man darüber dann auf ein Array Feld zugreifen kann
So würde

arr['A'] = 3

eine 3 in das 65te Feld des Arrays schreiben.

Nun wird einfach in einer Schleife über die Wörter gelaufen.
Um nur ein Array zu verwenden wird für jeden Buchstaben in Wort 1 der entsprechende Counter erhöht

chars[s1[i]]++;

und für jeden Buchstaben aus Wort 2 der Counter verringert

chars[s2[i]]--;

Somit, wenn die Wörter aus den selben Buchstaben bestehen muss der Counter in der Summe für jeden Buchstaben 0 ergeben.

das memset am Anfang ist nur dafür da um zunächst einmal alle Felder des Arrays zu nullen, bei Statischen Arrays ist der Speicher, welcher für das Array alloziiert wurde bereits beschrieben mit den werten die zuletzt dort lagen.

Ein kleiner Lauf mit den wörtern ABC und BCA:

1. Schleifendurchgang:
chars['A']++;
chars['B']--;
Damit ist:
chars[65] == 1
und
chars[66] == -1 (255)

2. Schleifendurchgang:
chars['B']++;
chars['C']--;
Damit ist:
chars[65] == 1
und
chars[66] == 0 (-1 + 1)
und 
chars[66] == -1 (255)

3. Schleifendurchgang:
chars['C']++;
chars['A']--;
Damit ist:
chars[65] == 0 (+1 - 1)
und
chars[66] == 0 (-1 + 1)
und 
chars[66] == 0 (-1 + 1)

Die anderen Felder wurden nie verwendet, daher sind alle Felder = 0 also ist es ein Anagramm

for (unsigned int i = 0; i < (sizeof(chars) / sizeof(chars[0])); i++)
		if (chars[i])
			return 0;

	return -1;

Macht nichts anderes als zu überprüfen:
Gehe jedes Feld durch, ist das feld != 0 (kürzer mit if (chars[i])) dann ist es kein Anagramm, und return 0 (false)
Wenn für jedes Feld der Wert = 0 war so wurde kein false returned, also return -1 (true)