Buchstabensortiererfunktion - Bbaktensoteuschonrtirferuni?

Leon++

ich habe folgende frage:

in Quizes(9Live) kommt häufig eine frage wie:

tntieenr - was ist gesucht?

Lösung wäre: internet

was für eine funktion müsste man schreiben um vertauschte buchstabe wieder zu einem wort zu machen. Ich stell mir so vor, dass die funktion alle kombinationen ausprobiert und diese mit einer wörterliste einer datei vergleicht. Fällt euch dazu etwas ein?

Du hast die Lösung doch schon genannt

davie

du sortierst die buchstaben im gesuchten wort alphabetisch (eeinrtt) und hast eine alphabetisch sortierte wortliste, wobei die eine art (multi)map ist, wobei jeder eintrag sein muss wie z.b. eeinrtt -> internet.
dann hast du für deine abfrage den befehl

typedef multimap<string,string> dictionary_t;
   for (dictionary_t::iterator i = dictionary.lower_bound("bar"); i != dictionary.upper_bound("bar"); ++i)
      cout << i->second;

und ersparst dir die lästigen permutationen.

Informier dich mal über Anagramme.
http://de.wikipedia.org/wiki/Anagramm
http://www.google.de/search?q=anagram+filetype%3Acpp

Werner Salomon

Hallo Leon,

es gibt einen Algorithmus 'next_permutation' mit dem man alle Möglichkeiten durchprobieren kann. Etwa so

#include <iostream>
#include <algorithm>    // sort, next_permutation
#include <string>

int main()
{
    using namespace std;
    string wort = "tntieenr";
    sort( wort.begin(), wort.end() );
    while( next_permutation( wort.begin(), wort.end() ) )
    {
        // .. suche Wort im Wörterbuch
        if( wort == "internet" )
            cout << "gefunden" << endl;
    }
    return 0;
}

Die vorhergehende Sortierung ist notwendig, da 'next_permutation' eine lexikalische Reihenfolge erzeugt und stoppt (return false) falls kein 'höheres' Wort mehr existiert. sort erzeugt das 'kleinste' mögliche Wort.

Ansonsten ist davie's Idee wahrscheinlich schneller.

Gruß
Werner

Leon++

typedef multimap<string,string> dictionary_t; 
   for (dictionary_t::iterator i = dictionary.lower_bound("bar"); i != dictionary.upper_bound("bar"); ++i) 
      cout << i->second;

Das versteh ich nicht.

Ich würde jetzt spontan eine funktion schreiben die das wort "tntieenr" und alle Wörter im Dictionary alphabetisch ordnet und dann vergleicht.

1. alphabetischOrdnen-Funktion ist kein problem
2. doch wie vergleiche ich "tntieenr" mit den Wörtern im Dictionary
3. woher kriege ich eine Datei die einen duden erstzt (selbst schreiben dauert zu lange.

davie

3. googlen brachte z.b. das: http://j3e.de/ispell/igerman98/dict/

2. wenn du den standardcontainer map (bzw. multimap) kennst, dann kannst du diesen für dich einsetzen.

1. hoffentlich.

so spontan hätte ich sowas gemeint und wenn ich mich jetzt nicht vertan habe, müsste das passen:

#include <iostream>
#include <map>
#include <algorithm>
#include <fstream>
#include <string>
using namespace std;

typedef multimap<string, string> dict_t;

string get_word (string const& line) //nur eine behelfsfunktion um die eingabedaten aus dem german98-format richtig zu lesen. im besten fall (eigenes dateiformat) würde ein getline reichen.
{
   string ret;
   for (string::const_iterator i = line.begin(); i != line.end(); ++i)
   {
      if (*i == '/') break;
      else if (*i == '"') //ohne umlaute!
      {
         continue;
      }
      ret += tolower(*i); //aja, damit wir uns auf sicherem terrain bewegen.
   }
   return ret;
}

void load_dictionary (char const* filename, dict_t& dictionary) //schnell dahingeschlampt
{
   ifstream input(filename);
   string line;
   while (getline(input, line))
   {
      string word = get_word(line);
      string sorted = word;
      sort (sorted.begin(), sorted.end());
      dictionary.insert (make_pair(sorted, word)); //multimap ordnet uns alles von selbst, das ist praktisch.
   }

}

int main (int argc, char** argv)
{
   dict_t dictionary;
   for (int i = 1; i < argc; ++i)
   {
      cout << "Loading " << argv[i] << "...\n" << flush;

      load_dictionary(argv[i], dictionary);
   }

   cout << "\nBitte geben Sie das gesuchte Anagramm ein: ";
   string anagram;
   cin >> anagram;

   int (*ptr) (int) = tolower;
   transform (anagram.begin(), anagram.end(), anagram.begin(), ptr); //kleinbuchstaben sind toll.

   sort(anagram.begin(), anagram.end());

   cout << "Übereinstimmung(en) mit:\n"; //und weil multimap schön geordnet ist müssen wir sie nur mehr abfragen und nichts selbst tun.
   for (dict_t::iterator i = dictionary.lower_bound(anagram); i != dictionary.upper_bound(anagram); ++i)
      cout << '\t' << i->second << endl;

}

wenn du die container nicht kennst, musst du

a) eine andere lösung dir selbst überlegen

oder

b) mit ihnen umgehen lernen (multimap ist allerdings imo nicht gerade der beste einstieg...)

Leon++

ich nehme a)

volkard

ich halte eure lösungen irgendwie für nicht einfach genug.

zunächst mußt du eine möglichst große wortliste haben. schau im internet unter "wordlist" oder so nach. bei den hackern. die benutzen die, um passwörter zu raten.

die sieht ungefähr so aus:

...
not
notar
note
...

und alles, was du machen mußt, ist ein programm schreiben, das das sortierte wort vor das wort schreibt

int main(){
   string str;
   while(getline(cin,str)){
      string sorted=str;
      sort(str.begin(),str.end());
      cout<<sorted<<' '<<str<<'\n;
   }
}

aufruf mit deinProg < wordlist.txt > pairlist.txt

...
not not
anort notar
enot note
...

und das jagste noch durch

sort < pairlist.txt > sortedPairlist.txt

fertig.

guckste jetzt 9-live und sie fragen nach "vaklord" dann öffneste du diue datei in deinem editor und tippst Strg-F (suchen) und "vldrako " (das leerzeichen ist nötig, um zu schauen, ob du die einzige lösung hast) und der cursor hüpft auf die zeile

vldrako volkard

Leon++

[quote"davie"]googlen brachte z.b. das: http://j3e.de/ispell/igerman98/dict/ [/quote]

habe ich heruntergeladen, gefällt mir nicht, vor jedem wort ist eine zeichenkette wie

8/cAachen
/b6Aal